Задача 67499
|
|
 |
Условие
В классе $N$ школьников, среди них образовалось несколько компаний. Общительностью школьника назовём количество людей в наибольшей компании, куда он входит (если ни в одну не входит, то общительность равна $1$). Оказалось, что у всех девочек в классе общительность разная. Каково наибольшее возможное количество девочек в классе?Решение
Уточним, что под наибольшей компанией для школьника подразумевается компания с наибольшим числом школьников в ней (таких может быть несколько).Оценка. Пусть в классе $k$ девочек. Девочка с наибольшей общительностью входит в компанию, где не меньше $k$ человек. Других девочек в этой компании нет. Значит, в классе не менее $k - 1$ мальчиков. Следовательно, $k + (k - 1) \leqslant N$, то есть $k \leqslant \left[\frac{N+1}2\right] $.
Пример. При $k = \left[\frac{N+1}2\right]$ занумеруем девочек числами от 1 до $k$, мальчиков – числами от $k + 1$ до $N$ и создадим $k$ компаний: в $i$-ю компанию входят $i$-я девочка и $i - 1$ мальчиков с наименьшими номерами.
