Азиатско-Тихоокеанская математическая олимпиада, 2008 год

Ученики в классе формируют группы, каждая из которых содержит ровно 3 ученика, таким образом, что любые две различные группы имеют не более одного ученика в общем. Докажите, что если в классе 46 учеников, то найдется множество из 10 учащихся в котором ни одна группа строго не содержится.

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

Будем доказывать задачу по индукции. Покажем, что мы можем выбрать $k, \, 3 \leq k \leq 10$ учеников так, что среди них нет полной группы.

База: $k=3$. Если любые три ученика образуют группу, то нарушается условие о том, что группы пересекаются не более чем по $1$ ученику.

Предположение: Для $k \leq 9$ мы можем выбрать $k$ учеников так, чтобы среди них не было полной группы.

Переход: Выберем $9$ учеников. Пусть мы добавили ученика $X$. Тогда если групп не образовалось, то мы решили задачу. Пусть появилась группа. Так как без $X$ групп не было, то $X$ в группе вместе еще с двумя учениками из $9$ которых мы уже выбрали. Так как любые две группы пересекаются не более чем по одному ученику, то никакая пара учеников не состоит более чем в одной группе. $9$ выбранных учеников образуют $\frac{9\cdot8}{2} = 36$ пар. Тогда не более $36$ учеников образуют с ними группы. А так как всего кроме выбранных учеников, $46 - 9 = 37$ учеников, то найдется хотя бы один которых не образует группу с уже выбранными учениками. То есть мы нашли искомых $10$ учеников.