Городская Жаутыковская олимпиада по математике, 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$, что противоречит условию.