Разделы 
Дополнительно
Задача по математике - 1807
2019-01-20 
В классе 30 учеников, и у каждого из них одинаковое число друзей среди одноклассников. Каково наибольшее возможное число учеников, которые учатся лучше большинства своих друзей? (Про любых двух учеников в классе можно сказать, кто из них учится лучше; если $A$ учится лучше $B$, а тот - лучше $C$, то $A$ учится лучше $C$).
Решение:
Учеников, которые учатся лучше большинства своих друзей, назовем хорошими. Пусть $x$ - число хороших учеников, $k$ - число друзей у каждого ученика.
Лучший ученик класса является лучшим в $к$ парах друзей, а любой другой хороший ученик - не менее, чем $\left [ \frac{k}{2} + 1 \geq \frac{k+1}{2} \right ]$ парах (здесь квадратные скобки обозначают целую часть числа). Поэтому хорошие ученики являются лучшими не менее, чем в $k + (x - 1) \frac{k+1}{2}$ парах. Это число не может превышать числа всех пар друзей в классе, равного $\frac{30k}{2} = 15k$. Отсюда $k + (x - 1) \frac{k+1}{2} \leq 15k,$ или
$x \leq 28 \cdot \frac{k}{k+1} +1$. (1)
Заметим далее, что
$\frac{k+1}{2} \ \leq 30 - x$, (2)
поскольку число учеников, лучше которых учится наихудший из хороших учеников, не превышает $30 - x$.
Правая часть неравенства (1) возрастает с ростом $к$, а неравенство (2) равносильно условию
$k \leq 59 - 2x$. (3)
Из (1) и (3) следует, что $x \leq 28 \cdot \frac{59 - 2x}{60 - 2x} +1$, или
$x^2 - 59x + 856 \geq 0$. (4)
Наибольшим целым $x$, удовлетворяющим (4) и условию $x \leq 30$, является $x = 25$. Итак, число хороших учеников не превышает 25.
Покажем, что оно может равняться 25. Занумеруем учеников числами от 1 до 30 в порядке ухудшения успеваемости и расположим номера в таблице $6 \times 5$ так, как показано на рис. Пусть пара учеников является парой друзей, если их номера расположены одним из трех способов: а) в соседних строках и в разных столбцах; б) в одном столбце и один из номеров при этом находится в нижней строке; в) в верхней строке. При этом, как нетрудно проверить, все требуемые условия выполнены.
Ответ. 25.
В классе 30 учеников, и у каждого из них одинаковое число друзей среди одноклассников. Каково наибольшее возможное число учеников, которые учатся лучше большинства своих друзей? (Про любых двух учеников в классе можно сказать, кто из них учится лучше; если $A$ учится лучше $B$, а тот - лучше $C$, то $A$ учится лучше $C$).
Решение:
Учеников, которые учатся лучше большинства своих друзей, назовем хорошими. Пусть $x$ - число хороших учеников, $k$ - число друзей у каждого ученика.
Лучший ученик класса является лучшим в $к$ парах друзей, а любой другой хороший ученик - не менее, чем $\left [ \frac{k}{2} + 1 \geq \frac{k+1}{2} \right ]$ парах (здесь квадратные скобки обозначают целую часть числа). Поэтому хорошие ученики являются лучшими не менее, чем в $k + (x - 1) \frac{k+1}{2}$ парах. Это число не может превышать числа всех пар друзей в классе, равного $\frac{30k}{2} = 15k$. Отсюда $k + (x - 1) \frac{k+1}{2} \leq 15k,$ или
$x \leq 28 \cdot \frac{k}{k+1} +1$. (1)
Заметим далее, что
$\frac{k+1}{2} \ \leq 30 - x$, (2)
поскольку число учеников, лучше которых учится наихудший из хороших учеников, не превышает $30 - x$.
Правая часть неравенства (1) возрастает с ростом $к$, а неравенство (2) равносильно условию
$k \leq 59 - 2x$. (3)
Из (1) и (3) следует, что $x \leq 28 \cdot \frac{59 - 2x}{60 - 2x} +1$, или
$x^2 - 59x + 856 \geq 0$. (4)
Наибольшим целым $x$, удовлетворяющим (4) и условию $x \leq 30$, является $x = 25$. Итак, число хороших учеников не превышает 25.
Покажем, что оно может равняться 25. Занумеруем учеников числами от 1 до 30 в порядке ухудшения успеваемости и расположим номера в таблице $6 \times 5$ так, как показано на рис. Пусть пара учеников является парой друзей, если их номера расположены одним из трех способов: а) в соседних строках и в разных столбцах; б) в одном столбце и один из номеров при этом находится в нижней строке; в) в верхней строке. При этом, как нетрудно проверить, все требуемые условия выполнены.
Ответ. 25.
