|
|
 |
Условие
В классе 30 учеников, и у каждого из них одинаковое число друзей среди одноклассников. Каково наибольшее возможное число учеников, которые учатся лучше большинства своих друзей? (Про любых двух учеников в классе можно сказать, кто из них учится лучше; если A учится лучше B, а тот – лучше C, то A учится лучше C.)
Решение
Учеников, которые учатся лучше большинства своих друзей, назовём хорошими. Пусть 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 ≤ 28·k/k+1 = 28 – 28/k+1 ≤ 28 – 28/8 = 24,5. Значит, и в этом случае n ≤ 25.
Покажем, что n может равняться 25. Занумеруем учеников числами от 1 до 30 в порядке ухудшения успеваемости и расположим номера в таблице 6×5 так, как показано на рисунке.
Пусть пара учеников является парой друзей, если их номера расположены одним из трёх способов: а) в соседних строках и в разных столбцах; б) в одном столбце и один из номеров при этом находится в нижней строке; в) в верхней строке. При этом, как нетрудно проверить, все требуемые условия выполнены.
Ответ
25 учеников.
