Задача 35512

Тема:    [ Принцип Дирихле (прочее) ]

Сложность: 3 Классы: 7,8,9

Условие

Докажите, что в любой компании найдутся два человека, имеющие одинаковое число друзей (из этой компании).

Подсказка

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

Решение

Пусть в компании n человек. Тогда у каждого человека имеется от 0 до  n – 1  друзей. Таким образом, количество друзей может принимать n различных значений:  0, 1, 2, ..., n – 1.  Поэтому если бы n человек имели различное число друзей, то в компании присутствовало бы по одному человеку, имеющему  0, 1, 2, ... , n – 1  друзей. С другой стороны, если есть человек, имеющий  n – 1  друга, то он дружит со всеми, следовательно, нет человека, который имеет 0 друзей. Противоречие.

Источники и прецеденты использования

web-сайт

задача