Районная олимпиада, 2008-2009 учебный год, 10 класс

В зале находятся $n>2$ человек. Доказать, что среди них найдутся 2 человека с одинаковым количеством знакомых.

Комментарий/решение

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