Паросочетания и лемма Холла

Подсказка 1

Попробуем реализовать следующую идею: возьмем три самых популярных языка (назовем их первым, вторым и третьим) и рассмотрим граф, в котором только эти три языка и все математики. Если найти в нем паросочетание, то распределить математиков на группы легко. А как доказать, что в этом графе есть паросочетание?

Подсказка 2

Рассмотрим любых k математиков. В случае k ≤ 100 условие леммы Холла очевидно. Попробуем разбить доказательство еще на два случая: 101 ≤ k ≤ 200 и 201 ≤ k ≤ 300. Предположим, что в первом из этих двух случаев условие леммы Холла не выполняется. Что тогда можно сказать о языковых знаниях математиков?

Подсказка 3

Действительно, условие леммы Холла не выполнится, только если все эти k математиков знают ровно 1 язык. Попробуем доказать, что это невозможно. Для этого пойдем от непопулярных языков: пусть пятый язык знают меньше всего людей. Если его знают более 100 человек, то четвертый язык - язык, который знают меньше всего людей после пятого, а в если не более 100 человек, то это язык, который знает меньше всего людей среди знающих пятый (в этот момент мы начинаем полагать, что 1, 2 и 3 языки являются просто всеми остальными). Теперь нам фактически нужно оценить число людей, знающих одновременно четвертый и пятый язык. Как это сделать?

Подсказка 4

Все верно! В первом случае это сразу ясно, а во втором это оценивается так: люди знают всего 900 языков (3 * 300 = 900), тогда пятый язык знают не более 900/5 < 200 человек, тогда эти люди знают менее 400 языков, помимо пятого, следовательно, сам четвертый язык знают менее 400/4 = 100 человек. Тогда невыполнение леммы Холла в случае 101 ≤ k <= 200 невозможно. А при каких условиях она может не выполняться для случая 201 ≤ k < 300?

Подсказка 5

Верно! Лемма Холла неверна, только если все эти k математиков не знают какой-то из языков: 1-ый, 2-ой или 3-ий. Однако меньше всего математиков знают пятый язык. Тогда в этом случае пятый язык знают менее ста человек. Как можно теперь доказать, что этот случай невозможен?

Подсказка 6

Пусть все эти k математиков не знают третий язык. Тогда его знает не более 300-k человек. Из наших k математиков не более 100 знают пятый язык, а можно ли тогда оценить число знающих четвертый язык и использовать условие его выбора для этой ситуации?