А это вот авторское решение.
Показать скрытый текст
Учеников, которые учатся лучше большинства своих друзей, назовем хорошими. Пусть n – число хороших учеников, k – число друзей у каждого ученика. Докажем, что n ≤ 25. Для этого разберем два случая.
1) k ≥ 8. Тогда пять худших учеников класса не являются хорошими.
2) k ≤ 7. Лучший ученик класса является лучшим в k парах друзей, а любой другой хороший ученик – не менее, чем в (k+1)/2 парах. Поэтому хорошие ученики являются лучшими не менее, чем в k+(n-1)(k+1)/2 парах. Это число не может превышать числа всех пар друзей в классе, равного 15k. Отсюда 2k + (n – 1)(k + 1) ≤ 30k, то есть n-1 ≤ 28k/(k+1) = 28 - 28/(k+1) ≤ 28 - 28/8 = 24,5
Значит, и в этом случае n ≤ 25.
Покажем, что n может равняться 25. Занумеруем учеников числами от 1 до 30 в порядке ухудшения успеваемости и расположим номера в таблице 6×5 так, как показано на рисунке.
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30
Пусть пара учеников является парой друзей, если их номера расположены одним из трех способов: а) в соседних строках и в разных столбцах; б) в одном столбце и один из номеров при этом находится в нижней строке; в) в верхней строке. При этом, как нетрудно проверить, все требуемые условия выполнены.
