32 подмножества

[Ktina]

В шестиэлементном множестве выбрано 32 подмножества, каждые три из которых имеют общий элемент. Докажите, что все эти подмножества имеют общий элемент.

[waxtep]

0. Пусть множество будет $\{1,2,3,4,5,6\}$ и подмножества выбираются без повторов (иначе утверждение неверно); попробуем построить контрпример:
1. Если мы возьмем хотя бы одно одноэлементное или двухэлементное подмножество, содержащее элемент $1$ - придется взять и оставшееся $31$ подмножество, содержащее $1$;
2. Тогда попробуем начать с трехэлементных; при этом, если мы возьмем подмножество $\{1,2,3\}$, то подмножество $\{4,5,6\}$ точно брать нельзя; значит, максимум можно взять $10$ трехэлементых подмножеств;
3. Но подмножеств с бОльшим количеством элементов не так много - всего $22$; т.е. для контрпримера придется взять ровно $10$ трёхэлементных и все подмножества с $4,5,6$ элементами;
4. Это значит, в частности, мы должны будем взять подмножества $\{1,2,3\},\{3,4,5,6\},\{1,2,4,5,6\}$ - но они не имеют общего элемента $\Rightarrow$ контрпример не получился!

[Gagarin1968]

Я думаю, что фишка в том, что не зря выбрана ровно половина всех подмножеств 6-элементного множества. Если в числе выбранных есть какое-то подмножество $M$, то понятно, что его дополнение $\overline{M}$ выбрано быть не может, ибо $M\cap \overline{M}=\varnothing$, а это противоречит условию. Получается, что из каждой пары дополняющих друг друга подмножеств выбрано ровно одно.
Теперь, если выбраны подмножества $M$ и $N$, то обязательно должно быть выбрано и их пересечение $\overline{M\cap N}$, т.к. иначе $M\cap N\cap \overline{M\cap N}=\varnothing$ - опять противоречие с условием.
А вот тут я тормознулся. Чувствую, что если мы выбираем какие-то подмножества, то должен быть какой-то индукционный переход на пересечение всех этих выбранных подмножеств, которое не может быть пустым. Но не вижу, как это сделать.
Зато я вижу, как сконструировать эти 32 подмножества. Берём какой-то один фиксированный элемент из шести, а затем выбираем все $32$ подмножества, в которых этот элемент содержится.

[worm2]

Gagarin1968, очень красивая идея!
Остался всего один маленький шаг: просто берём все выбранные множества по одному: $M_1$, $M_2$, $M_3$, $M_4$, $\dots$ и последовательно строим их пересечение $\bigcap M_i$. Мы либо получим, что пустое множество принадлежит набору (что противоречит условию), либо перечислим все множества, получив их непустое пересечение, ч.т.д.

[DeBill]

Gagarin1968 в сообщении #1424760 писал(а):

должен быть какой-то индукционный переход на пересечение всех этих выбранных подмножеств, которое не может быть пустым

Так Вы же его уже сделали: если пересечение двух выбранных также является выбранным, то тройное пересечение выбранных фактически есть двойное пересечение (пересечение "пересечения двух" с третьим). И т.д. - это в точости желаемая Вами индукция. Так что и шестерное пересечение не пусто, что и требовалось...

Более того, можно - как Вы и говорили - сделать и шажок дальше: коль есть общий элемент, а всего множеств, его содержащих - ровно 32, то все они и выбраны. Так что есть и пример, и его единственность (почти).

[Gagarin1968]

DeBill в сообщении #1424804 писал(а):

Так что есть и пример, и его единственность (почти).

DeBill
А можете пояснить эту вашу оговорку "почти". Почему?
Ведь если зафиксировать какой-то элемент из данного множества , то все $32$ подмножества, включающих этот элемент, выбираются строго единственным образом. Разве нет?

[DeBill]

Gagarin1968 в сообщении #1424850 писал(а):

Разве нет?

Да - ну, я , вроде так и написал. А "почти" относилось именно к тому - какой элемент из наших 6 зафиксировать...

[Gagarin1968]

Понял, спасибо.