ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73560
Темы:    [ Объединение, пересечение и разность множеств ]
[ Правило произведения ]
[ Разбиения на пары и группы; биекции ]
Сложность: 4+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

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

Решение

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

Замечания

1. Фактически, мы доказали, что условию задачи удовлетворяет только такая система подмножеств: фиксируется некоторый элемент a множества A и выбираются все подмножества, содержащие этот элемент.

2. Ср. с задачей 78718.

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1970
выпуск
Номер 5
Задача
Номер М25

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .