Графы, турниры и игры на СПБГУ

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

С другой стороны, по условию есть ученики, поздоровавшиеся ровно с

школьниками, и они не находятся среди Поэтому учеников в школе не меньше, чем

Таким образом, справедливы неравенства

Складывая их, мы получим

Покажем теперь, что реализуется. Разобьём всех учеников на две групшы: и Пусть поздоровался с при а остальные пары школьников не здоровались друт с другом. Проверим, что такой пример нам подходит.

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