Олимпиада Туймаада по математике. Младшая лига. 2009 год

Каждое из подмножеств $A_1$, $A_2$, $\dots$, $A_n$ 2009-элементного множества $X$ содержит не менее 4 элементов. Пересечение любых двух из этих подмножеств содержит не более 2 элементов. Докажите, что в $X$ можно найти 24-элеметное подмножество $B$, не содержащее ни одного из множеств $A_1$, $A_2$, $\dots$, $A_n$. ( из материалов олимпиад )

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

Во-первых, мы можем просто предположить, что $ |A_i|=4$. Если нет, мы можем заменить $ A_i$ на $ 4-элементное $ подмножество $ A_i$.

Случайным образом выбираем элемент $24$ из $X$, называем его $Y=\{1,2,...24\}$

Конечно, $Y$ может содержать некоторый $A_i$, обозначим $m$ количеством $A_i$ таких, что $A_i$ содержится в $Y$, ($m$, ​​очевидно, конечен)

Все, что нам нужно сделать, это уменьшить $m$ :D

WLOG пусть $A_1=\{1,2,3,4\}$ содержится в $Y$

Удаляем $1$, можем добавить элемент из $\{25,26,...2009\}$

После удаления $1$,$m$ уменьшится как минимум на $1$, если мы добавим $i$ в $Y$,$\{i,p,q,r\}$($i \in \{25, 26,...2009\},p,q,r \in \{1,2,...24\}$) не является ни одним из $ A_i$

Тогда все готово. Итак, для любого $ i \in \{25,26,...2009\}$ $ \ существует p,q,r,A_j$ так, что $ A_j=\{i,p,q,r \}$

Посчитаем возможные $A_j$. Легко показать, что таких $A_j$ не более $\binom{23}{3}$(потому что $ |A_i \cap A_j|\le 2$ и $ |A_j| =4$)

но из $ \{25,26,...2009\}$ нам разрешено выбрать $ 1985$, которое больше $ \binom{23}{3}$

Противоречие!