2015-03-19
В зале находится $n \geq 2$ человек.
Докажите, что в зале найдутся два человека, которые имеют
среди присутствующих одинаковое число знакомых (предполагаем, что, если $A$ — знакомый $B$, тогда $B$ — знакомый $A$; не считаем никого знакомым самому себе).
Решение:
He будем рассматривать тех, которые не имеют ни одного знакомого в зале (и поэтому сами не являются знакомыми кому-нибудь из присутствующих). Если их число больше двух, теорема доказана. Пусть останется $k$ человек, каждый из которых имеет не менее одного знакомого. Очевидно, $k \geq 2$, каждый может иметь $1, 2, \cdots , k-1$ знакомых, но так как присутствующих в зале $k$, то, очевидно, по крайней мере двое имеют одинаковое число знакомых.