Processing math: 87%

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


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

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

пред. Правка 2   7
1 года 3 месяца назад #

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

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