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

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

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

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

То значит что у людей будет от 0 до n-1 знакомых, а это невозможно, ибо человек с n-1 знакомыми знаком со всеми, и так же с человеком с 0 знакомыми.

Это классическая задача из теории графов, известная как задача о праздничных рукопожатиях. Мы можем решить её, предположив обратное, и использовать принцип Дирихле. Предположим, что каждый человек имеет разное количество знакомых. Пусть человек с наименьшим количеством знакомых имеет не менее, чем 1 знакомого, а человек с наибольшим количеством знакомых имеет не более, чем (n-1) знакомого. Тогда есть (n-1) человек, и каждый из них имеет от 1 до (n-1) знакомых. Это противоречит начальному условию, что всего n человек в зале. Следовательно, как минимум два человека должны иметь одинаковое количество знакомых.