Городская Жаутыковская олимпиада по математике, 8 класс, 2024 год

Мектепте 2024 оқушы оқиды, олардың кейбірі бір-бірімен дос. Әр оқушының достар саны 40-тан аспайтыны белгілі. Араларында ешкім ешкіммен дос емес 50 оқушы табылатынын дәлелдеңіз.

Комментарий/решение

Решение. Рассмотрим наибольшую по численности группу людей $A$, в которой никто ни с кем не дружит. Предположим, что утверждение задачи неверно, тогда в этой группе $k$ людей, где $k$ $\leq$ $49$. Рассмотрим остальных $2024 - k$ людей, назовём их группой $B$. Каждый из $B$ должен иметь хотя бы одного друга в $A$ (иначе его можно было бы добавить в $A$, увеличив эту группу). Значит, дружб между группами $A$ и $B$ хотя бы $2024 - k$. Тoгда по принципу Дирихле в $A$ найдётся человек, у которого друзей хотя бы $\frac{2024-k}{k}$ $=$ $\frac{2024}{k}$ $-$ $1$ $\geq$ $\frac{2024}{49}$ $>$ $40$, что противоречит условию.