Олимпиада им. Эйлера

Подсказка 1

Ясно, что достаточно показать, что из любой группы, в которой больше 49 ребят, можно удалить одного так, что группа останется популярной. Предположим, что в популярной группе с не менее, чем 50 участниками, после удаления любого участника нарушается популярность. Как теперь можно естественным образом разбить участников новой группы на 2 вида?

Подсказка 2

Верно! Одна группа — те, для которых есть знакомые не в этой группе, причем эти знакомые знают только с этим человеком из нашей группы. Вторая группа — те, кто не знаком ни с кем из нашей группы, а только с остальными ребятами. Попробуем теперь посчитать общее число знакомств ребят из нашей группы с остальными ребятами. Как это сделать?

Подсказка 3

Пусть A₁ — множество ребят первого вида, а A₂ — множество ребят второго вида, а B — множество остальных ребят. Тогда количество знакомств ребят из нашей популярной группы с ребятами из B не меньше |A₁| + k|A₂|. Эта оценка использовала соображения о том, с кем знакомы ребята из популярной группы. А можно ли теперь оценить число знакомств сверху, если посмотреть на ребят из B?

Подсказка 4

Можно! Для этого каждому школьнику первого вида сопоставим кого-то из B, который знаком только с ним и группу этих ребят назовем B₁, а остальных из B назовем B₂. Как тогда получить верхнюю оценку?

Подсказка 5

Конечно! Тогда знакомств между популярной группой и B не более |B₁|+k|B₂|. Тогда у нас есть неравенство |A₁| + k|A₂| ≤ |B₁|+k|B₂|. Как теперь получить противоречие?