Докажите, что в любой компании из пяти человек двое имеют одинаковое число знакомых.

Доказательство.

Докажем утверждение с помощью принципа Дирихле.

Рассмотрим компанию из пяти человек. Будем считать, что знакомство взаимно: если человек А знаком с человеком Б, то и человек Б знаком с человеком А.

Каждый человек может иметь в этой компании от 0 до 4 знакомых, поскольку всего в компании 5 человек и сам с собой человек не считается знакомым.

Таким образом, возможное число знакомых у каждого человека:

0, 1, 2, 3 или 4.

На первый взгляд кажется, что все пять человек могут иметь разное число знакомых. Однако заметим важное обстоятельство:

• Если в компании есть человек, у которого 0 знакомых, то не может быть человека, у которого 4 знакомых, так как последний должен быть знаком со всеми, в том числе и с первым.

• Если же в компании есть человек, у которого 4 знакомых, то не может быть человека, у которого 0 знакомых, поскольку с первым знакомы все остальные.

Следовательно, числа 0 и 4 не могут одновременно встречаться среди количеств знакомых участников компании.

Значит, у пяти человек возможны не более четырёх различных количеств знакомых:

• либо 0, 1, 2, 3;

• либо 1, 2, 3, 4.

Теперь применим принцип Дирихле: если пять объектов распределены по четырём группам, то хотя бы в одной группе окажутся не менее двух объектов.

В нашем случае пять человек распределяются по четырём возможным значениям числа знакомых. Следовательно, хотя бы у двух человек число знакомых обязательно совпадёт.

Что и требовалось доказать.