|
|
 |
Условие
В множестве, состоящем из n элементов, выбрано 2n–1 подмножеств, каждые три из которых имеют общий элемент.
Докажите, что все эти подмножества имеют общий элемент.
Решение
Всего в множестве A, состоящем из n элементов, существует 2n различных подмножеств, считая пустое множество и само множество A.
Дополнение подмножества B будем обозначать B. По условию выбрано 2n–1 подмножеств, то есть половина всех возможных, причём пересечение любых двух (и даже трёх) из них не пусто. Следовательно, из каждой пары подмножеств (B, B) выбрано в точности одно. Далее, если B и C выбраны, то D = B ∩ C тоже выбрано, поскольку D не может быть выбрано (B ∩ C ∩ D пусто). Теперь по индукции можно доказать, что если B1, B2, ..., Bk выбраны, то и B1 ∩ B2 ∩ ... ∩ Bk тоже выбрано. Следовательно, пересечение всех 2n–1 выбранных подмножеств тоже принадлежит к числу выбранных и поэтому не пусто.
Замечания
1. Фактически, мы доказали, что условию задачи удовлетворяет только такая система подмножеств: фиксируется некоторый элемент a множества A и выбираются все подмножества, содержащие этот элемент.
2. Ср. с задачей 78718.
