Question

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

Answer 1

Представим учеников и отношение знакомства в виде графа. Найдем вершину $A$ наибольшей степени $m$. Пусть вершина $B$ инцидентна $A$ и имеет наибольшую степень $m'$ среди остальных вершин-соседей $A$. Если $m'<m$, то по принципу Дирихле найдутся две вершины с одинаковой степенью, а у них есть общая вершина — $A$, противоречие. Поскольку $m$ максимально, то $m=m'$. Итак, у нас ровно $m$ вершин, причем их степени различны и не превосходят $m$, следовательно, они пробегают все значения от $1$ до $m$. Вершина степени $1$ и является искомой.