Распечатать запись Распечатать запись

Теорема Холла, или теорема о свадьбах

Филип Холл

Филип Холл (Philip Hall, 1904–1982) — английский математик, большая часть работ которого относится к теории групп и связанным с ней разделам алгебры. Так, первая теорема Холла относится к разрешимым группам. Теорема Холла о свадьбах, доказанная им в 1935 году, является одним из основных комбинаторных принципов. Возможно, самый важный его вклад в математику — полиномы Холла, которые играют важную роль в теории представлений групп.

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

Перенумеруем юношей и девушек числами от 1 до n. Номера девушек запишем по строкам, номера юношей — по столбцам. Элемент, стоящий в i-й строке и j-м столбце таблицы равен 1 тогда и только тогда, когда брак между девушкой с номером i и юношей с номером j возможен, и 0 в противном случае. Иногда все девушки могут выйти замуж, а иногда поженить всех невозможно.

Приведу пример такой таблицы. Пусть юношей четверо и девушек тоже четверо. Пусть первой девушке нравятся первый и третий юноши, второй — первый и второй, третьей — второй, третий и четвертый, четвертой — первый и четвертый.

\begin{tabular}{c|cccc}<br />
&1&2&3&4\\<br />
\hline<br />
1&1&0&1&0\\<br />
2&1&1&0&0\\<br />
3&0&1&1&1\\<br />
4&1&0&0&1<br />
\end{tabular}

В данном случае можно поженить девушек и юношей с одинаковыми номерами.

Условие, необходимое и достаточное для того, чтобы всех можно было поженить, можно сформулировать несколькими эквивалентными способами:

1. Каждым r девушкам, 1\le r\le n нравятся по крайней мере n юношей.

Возьмем любые r строк. Найдем столбцы, которые содержат хотя бы одну 1 в выбранных строках. Число таких столбцов не должно быть меньше, чем r.

2. Каждым r юношей 1\le r\le n нравятся по крайней мере r девушек.

Возьмем любые r столбцов. Найдем строки, которые содержат хотя бы одну 1 в выбранных столбцах. Число таких строк не должно быть меньше, чем r.

3. В таблице не содержится подтаблицы, состоящей из одних нулей, из s строк и r столбцов такой, что s+r> n.

Если такая таблица существует, то некоторые s девушек могут вступить в брак только с n-r юношами вне подтаблицы. Так как r>n-s, юношей слишком мало, чтобы выдать замуж всех s девушек.

Теорема Холла. Условия 1, 2, 3 являются необходимыми и достаточными, чтобы можно было всех поженить.

Доказательство. Необходимость очевидна.

Достаточность докажем по индукции. В случае n=1, когда есть всего одна пара и взаимная симпатия, требуется простая формальность, чтобы договориться о браке. Предположим теперь, что теорема верна для всех k, таких что k< n. В случае n девушек и юношей может быть так, что каждым r (0< r< n) девушкам нравятся больше r юношей, а может быть, что им нравятся ровно r юношей. В первом случае первая девушка может выйти замуж за любого из тех, кто ей нравится, и тогда условие теоремы по-прежнему будет выполняться, но уже для n-1 девушки и n-1 юноши. Действительно, пусть каждым 0< r< n девушкам нравятся больше, чем r юношей. Один из этих юношей, возможно, был тот, кто женился на первой девушке. Но без него еще есть по крайней мере r юношей, которые нравятся r девушкам. Таким образом, после женитьбы любой пары остается n-1 девушка и n-1 юноша, для которых условие теоремы по-прежнему выполняется. По индукционному предположению, всех можно поженить.

Во втором случае есть r< n девушек, которым нравятся ровно r юношей. По индукционному предположению, мы можем выдать замуж этих девушек за тех r юношей, которые им нравятся. Хитрость заключается в том, чтобы показать, что остальных девушек тоже можно выдать замуж за оставшихся юношей. Рассмотрим любых s из оставшихся n-r девушек. r замужним девушкам плюс этим s девушкам должны нравиться по крайней мере r+s юношей, по условию теоремы. Так как r замужним девушкам не нравятся другие юноши кроме тех r, с которыми они состоят в браке, s девушкам должны нравиться другие юноше, не те, что женаты. Таким образом, оставшиеся n-r девушек могут заключить брак с неженатыми юношами, так как для них также выполнено условие теоремы. Тем самым, всех можно поженить.

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

Источник: http://www.cut-the-knot.org/arithmetic/elegant.shtml

Оставьте свой отзыв

Добавить изображение