2.10. Принцип Дирихле

Пусть ― функция, причем как так и ― конечные множества. Предположим, что множество состоит из элементов: . Принцип Дирихле гласит, что если , то, по крайней мере, одно значение встретится более одного раза, т.е. найдется пара элементов , для которых .

Допуская некоторую вольность, принцип Дирихле можно сформулировать в легко запоминающейся форме: нельзя рассадить 10 кроликов в 9 клеток, так чтобы в каждой клетке сидел только один кролик.

Пример. Покажите, что какие бы пять цифр из 1,2,3,4,5,6,7,8 мы ни выбрали, найдутся хотя бы две из них, сумма которых равна 9.

Решение. Перечислим пары цифр в сумме дающих 9: .

Обозначим через множество произвольно выбранных 5 цифр, а через следующее множество пар . Ясно, что . Рассмотрим функцию , сопоставляющую каждой цифре из пятерки пару из множества , которая в ней содержится. Например, . По принципу Дирихле хотя бы две цифры из множества попадут в одну и ту же пару. Короче говоря, две из пяти цифр дадут в сумме 9.

Принцип Дирихле можно обобщить следующим образом. Рассмотрим функцию , где и ― конечные множества. Если для некоторого натурального числа , то найдется такое значение функции , которое она будет принимать, по крайней мере раз.

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

Решение. Пусть ― один из шести человек, ― множество оставшихся пяти людей в группе и . Определим функцию по правилу

.

Поскольку , то найдется три человека, которые либо все знакомы с , либо все трое его не знают.

Предположим теперь, что три человека знакомы с . Если все трое друг с другом не знакомы, то мы получили решение задачи. В противном случае, какая-то пара, например, и знают друг друга. Но они же знакомы и с . Стало быть, трое людей знают друг друга. Аналогично разбирается случай, когда три человека не знакомы с .