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

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

Рассмотрим двудольный граф, вершинами левой доли будут математиков, вершинами правой доли будут и языки, причём у каждого языка будет по клонов. Также проведём рёбра от математиков ко всем языкам, которые они знают. Заметим, что от каждого математика ведёт хотя бы рёбер. Следовательно, от любых математиков ведёт или рёбер. Докажем, что для полученного графа выполнено условие леммы Холла. Рассмотрим любых математиков. Если то условие леммы Холла выполнено. Если то условие леммы Холла не выполнено только в случае, когда эти математиков знают один и тот же язык. Но в этом случае эти математиков знают один и тот же набор из трёх языков, два из которых это и языки. Следовательно, это случай (b). Но это невозможно, так как людей, знающих одновременно и язык меньше Если то условие леммы Холла не выполнено только в случае, когда эти математиков не знают какой-то из и языков. Пусть все эти математиков не знают третий язык. Но язык знают меньше всего людей, значит это случай (a). Но тогда язык знает не более людей, а из людей, не знающих третий язык не более знают язык. Значит язык знает не менее Осталось заметить, что что противоречит выборы языка в случае (a). Мы доказали, что для рассматриваемого графа есть паросочетание, покрывающее долю математиков, а это и есть разбиение их на группы по человек с общим языком.