Олимпиада Туймаада по математике. Младшая лига. 2009 год
Комментарий/решение:
Во-первых, мы можем просто предположить, что |Ai|=4. Если нет, мы можем заменить Ai на 4−элементное подмножество Ai.
Случайным образом выбираем элемент 24 из X, называем его Y={1,2,...24}
Конечно, Y может содержать некоторый Ai, обозначим m количеством Ai таких, что Ai содержится в Y, (m, очевидно, конечен)
Все, что нам нужно сделать, это уменьшить m :D
WLOG пусть A1={1,2,3,4} содержится в Y
Удаляем 1, можем добавить элемент из {25,26,...2009}
После удаления 1,m уменьшится как минимум на 1, если мы добавим i в Y,{i,p,q,r}(i∈{25,26,...2009},p,q,r∈{1,2,...24}) не является ни одним из Ai
Тогда все готово. Итак, для любого i∈{25,26,...2009} существуетp,q,r,Aj так, что Aj={i,p,q,r}
Посчитаем возможные Aj. Легко показать, что таких Aj не более \binom{23}{3}(потому что |A_i \cap A_j|\le 2 и |A_j| =4)
но из \{25,26,...2009\} нам разрешено выбрать 1985, которое больше \binom{23}{3}
Противоречие!
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.