Математикадан «Туймаада» олимпиадасы. Кіші лига. 2009 жыл

2009 элементтен тұратын $X$ жиынының ${{A}_{1}}$, ${{A}_{2}}$, $\ldots$, ${{A}_{n}}$ ішкі жиындары кем-дегенле төрт мүшеден тұрады. Кез-келген екі ішкі жиынның қиылысуында ең көп дегенде 2 элемент бар. $X$ жиынында, ${{A}_{1}}$, ${{A}_{2}}$, $\ldots$, ${{A}_{n}}$ жиындарының ешқайсысын қамтымайтын, 24 элементтен тұратын $B$ жиыны бар екенін дәлелдеңіз. ( из материалов олимпиад )

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

Во-первых, мы можем просто предположить, что $ |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}$

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