Олимпиада имени Леонарда Эйлера 2019-2020 учебный год, I тур заключительного этапа

В лагерь приехали 99 школьников, причём все приехавшие имеют одно и то же ненулевое количество знакомых среди остальных. Группу ребят, обладающую тем свойством, что любой из приехавших, не входящий в эту группу, знаком с кем-то из этой группы, будем называть популярной. Докажите, что из любой популярной группы, содержащей более 49 ребят, можно выбрать популярную группу, содержащую ровно 49 ребят. ( С. Берлов )

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

Пусть каждый школьник знает ровно $k$ человек. Тогда пусть $A$ какая-то популярная группа из более чем $49$ участников. Покажем, что мы можем убрать некоторого участника из $A$ так, что $A$ останется популярной. Предположим, что это не так. Тогда все участники из $A$ делятся на подгруппы $B, C$. Где любой школьник из $B$ не знаком не с одним из $A$, а любой школьник из $C$ является единственным знакомым из $A$ для кого-то не из $A$. Тогда школьники не состоящие в $A$ делятся на две подгруппы $E, F$. Где любой школьник из $F$ знает не более одного из $A$ такого, что этот знакомый из $C$, а каждый из $E$ знает хотя бы одного из $A$ кроме тех, что в $C$. Тогда $|F| \geq |C|$, так как в $F$ состоят все те кто имеет ровно одного знакомого из $A$. Также $|E| \geq |B|$ так как из каждого из $B$ выходит ровно по $k$ знакомств в $E$. Тогда $|A| = |B|+|C| \leq |E|+|F| = 99-|A| \Rightarrow |A| \leq 49$, противоречие. Значит мы всегда можем уменьшить размер популярной группы, пока он не станет равен $49$.