Теорема холу, або теорема про весіллях, математика, яка мені подобається

Філіп Холл (Philip Hall, 1904-1982) - англійський математик, велика частина робіт якого відноситься до теорії груп і пов'язаним з нею розділах алгебри. Так, перша теорема Холла відноситься до вирішуваним групам. Теорема Холла про весіллях, доведена їм в 1935 році, є одним з основних комбінаторних принципів. Можливо, найважливіший його внесок в математику - поліноми Холла, які відіграють важливу роль в теорії зображень груп.

У задачі про весіллях потрібно одружити кожну з дівчат з одним з юнаків. Кожна дівчина (після довгих і виснажливих сумнівів і обговорень) представляє список юнаків, які їй подобаються. Ми також зробимо припущення, що всі юнаки досить благородні для того, щоб не розбивати серце дівчини, яка вибрала його, своєю відмовою. Таким чином, хоча дівчата проявляють ініціативу, висловлюючи свої переваги, ситуація цілком симетрична і найкраще представляється таблицею, що складається з нулів і одиниць.

Перенумеруем юнаків і дівчат числами від до. Номери дівчат запишемо по рядках, номера юнаків - по стовпцях. Елемент, що стоїть в -му рядку і -м стовпці таблиці дорівнює тоді і тільки тоді, коли шлюб між дівчиною з номером і юнаків з номером можливий, і в іншому випадку. Іноді всі дівчата можуть вийти заміж, а іноді одружити всіх неможливо.

Наведу приклад такої таблиці. Нехай юнаків четверо і дівчат теж четверо. Нехай першої дівчині подобаються перший і третій юнаки, другий - перший і другий, третій - другий, третій і четвертий, четвертої - перший і четвертий.

1234 \\
\ hline
11010 \\
21100 \\
30111 \\
41001
\ End "title =" \ begin
1234 \\
\ hline
11010 \\
21100 \\
30111 \\
41001
\ End "style =" vertical-align: -52px; border: none; ">

В даному випадку можна одружити дівчат і юнаків з однаковими номерами.

Умова, необхідне і достатнє для того, щоб усіх можна було одружити, можна сформулювати кількома еквівалентними способами:

1. Кожним дівчатам, подобаються принаймні юнаків.

Візьмемо будь-які рядків. Знайдемо стовпці, які містять хоча б одну в обраних рядках. Число таких стовпців не повинно бути менше, ніж.

2. Кожним юнаків подобаються принаймні дівчат.

Візьмемо будь-які стовпців. Знайдемо рядки, які містять хоча б одну в обраних шпальтах. Число таких рядків не повинно бути менше, ніж.

3. У таблиці не міститься підтаблиці, що складається з одних нулів, з рядків і стовпців такий, що.

Якщо така таблиця існує, то деякі дівчат можуть вступити в шлюб тільки з юнаками поза підтаблиці. Так як, юнаків занадто мало, щоб видати заміж усіх дівчат.

Теорема Холла. Умови 1, 2, 3 є необхідними і достатніми, щоб можна було всіх одружити.

Доведення. Необхідність очевидна.

Достатність доведемо по індукції. У разі, коли є всього одна пара і взаємна симпатія, потрібна проста формальність, щоб домовитися про шлюб. Припустимо тепер, що теорема вірна для всіх, таких що. У разі дівчат і юнаків може бути так, що кожним () дівчатам подобаються більше юнаків, а може бути, що їм подобаються рівно юнаків. У першому випадку перша дівчина може вийти заміж за будь-якого з тих, хто їй подобається, і тоді умова теореми як і раніше буде виконуватися, але вже для дівчини і юнаки. Дійсно, нехай кожним дівчатам подобаються більше, ніж юнаків. Один з цих юнаків, можливо, був той, хто одружився на першій дівчині. Але без нього ще є принаймні юнаків, які подобаються дівчатам. Таким чином, після одруження будь-якої пари залишається дівчина і хлопець, для яких умова теореми як і раніше виконується. За індукційному припущенням, всіх можна одружити.

У другому випадку є дівчат, яким подобаються рівно юнаків. За індукційному припущенням, ми можемо видати заміж цих дівчат за тих юнаків, які їм подобаються. Хитрість полягає в тому, щоб показати, що інших дівчат теж можна видати заміж за що залишилися юнаків. Розглянемо будь-яких з решти дівчат. заміжнім дівчатам плюс цим дівчатам повинні подобатися принаймні юнаків, за умовою теореми. Так як заміжнім дівчатам не подобаються інші юнаки крім тих, з якими вони перебувають у шлюбі, дівчатам повинні подобатися інші юнакові, не ті, що одружені. Таким чином, залишилися дівчат можуть укласти шлюб з неодруженими юнаками, так як для них також виконана умова теореми. Тим самим, всіх можна одружити.

Завдання про весіллях можна також представити за допомогою графа. Цей граф двочастковий (всі його вершини можна розбити на два безлічі так, що ребра з'єднують лише вершини з різних множин). Дівчат позначати вершини в одному безлічі, юнаків - в іншому, ребрами з'єднаємо вершини, відповідні дівчині і хлопцю, які подобаються один одному. Тепер намалюємо замість таблиці, наведеної на початку статті, граф: