Условие
В классе 30 учеников, и у каждого из них одинаковое число друзей среди одноклассников. Каково наибольшее возможное число учеников, которые учатся лучше большинства своих друзей? (Про любых двух учеников в классе можно сказать, кто из них учится лучше.)
Ответ: 25.
Решение
Учеников, которые учатся лучше большинства своих друзей, назовем хорошими. Пусть [latex]x[/latex] — число хороших учеников, [latex]k[/latex] — число друзей у каждого ученика. Лучший ученик класса является лучшим в [latex]k[/latex] парах друзей, а любой другой хороший ученик — не менее, чем в [latex][k/2]+1 \geqslant (k+1)/2[/latex] парах (здесь квадратные скобки обозначают целую часть числа). Поэтому хорошие ученики являются лучшими не менее чем в [latex]k+(x-1)(k+1)/2[/latex] парах.
Это число не может превышать числа всех друзей в классе, равного [latex]30k/2=15k[/latex]. Отсюда [latex]k+(x-1)(k+1)/2 \leqslant 15k[/latex] или
[latex]x\leq28\frac{k}{k+1}+1[/latex] [latex](1)[/latex]
Заметим далее, что
[latex]\frac{k+1}{2}\leq30-x[/latex] [latex](2)[/latex]
поскольку число учеников, лучше которых учится наихудший из хороших, не превышает 30.
Правая часть неравенства [latex](1)[/latex] возрастает с ростом [latex]k[/latex], а неравенство [latex](2)[/latex] равносильно условию
Из [latex](1)[/latex] и [latex](3)[/latex] следует, что [latex]x\leq28*\frac{59-2x}{60-2x}+1[/latex], или
Наибольшим целым [latex]x[/latex], удовлетворяющим [latex](4)[/latex] и условию [latex]x \leq 30[/latex], является [latex]x=25[/latex]. Итак, число хороших учеников не превышает 25, что можно проиллюстрировать на графике.
Покажем, что оно может равняться 25. Занумеруем учеников числами от 1 до 30 в порядке ухудшения успеваемости и расположим номера в таблице [latex]6\times 5[/latex] так, как показано на рисунке.
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 |
Пусть пара учеников является парой друзей, если их номера расположены одним из трех способов:
- в соседних строках и в разных столбцах;
- в одном столбце и один из номеров при этом находится в нижней строке;
- в верхней строке.
При этом, как нетрудно проверить все требуемые условия выполнены.