Комбинаторика.

[Darts501]

Помогите решить задачу. Дано множество $A$, с мощностью равной $|A|=20$, также имеется совокупность $S=\{A_1,\dots,A_{10}\}$ 10-элементных подмножеств множества $A$, то есть $A_i \subset A$ и $|A_i|=10, \forall i=1,\dots 10$. Требуется доказать, что $\exists i,j : |A_i\cap A_j|\ge 5$.

В объединение $\relax \cup _{i=1}^{n}A_i$ лежит 100 элементов с учетом кратности. Теперь если мы избавимся от кратных элементов, оставив только по одному экземпляру у нас получится $A$ или некоторое его подмножество. Теперь надо показать, что если любые два $A_i,A_j$ пересекаются не более по 4 элементам, то в объединении должно получится больше 20 элементов, и это докажет задачу. Вот как это сделать не совсем понятно. Попробовав выбирать эти подмножества, мне показалось что вообще таких пар должно быть довольно много, или есть пары которые очень сильно пересекаются.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

Принцип Дирихле используйте.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[provincialka]

Собственно, недавно были похожие темы... от участника 2old

-- 12.10.2015, 13:41 --

Я там в одной теме давала совет. Там он не подошел... Проверьте, может в вашей задаче поможет?