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

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

Условие

При каком наименьшем n для любого набора A из 2007 множеств найдется такой набор B из n множеств, что каждое множество набора A является пересечением двух различных множеств набора B ?

Решение

Пусть набор A содержит множества A_1 , A_2 , A_{2007} . Включим в набор множества B1=A1 , B2=A2 , B2007=A2007 , B2008=A1 A2 ... A2007{x} (здесь x – элемент, не принадлежащий ни одному из множеств Ai ). Тогда все множества Bi разные, и Ai=B2008 Bi для i=1, 2, ... , 2007 . Далее, докажем, для множеств A1={1} , A2={1, 2} , A3={1, 2, 3} , A2007={1, 2, ..., 2007} в любом наборе B, удовлетворяющем условию, не менее 2008 множеств. Из условия вытекает, что для каждого i=1, 2, , 2006 среди множеств набора найдется множество Bi , содержащее Ai , но не содержащее Ai+1 (иначе Ai не может быть пересечением множеств набора B); заметим, что B_i также содержит все множества A_1, A_i и не содержит ни одного из множеств A_{i+1},A_n ; поэтому все множества B_i разные. Кроме того, среди множеств набора найдутся два множества B2007 и B2008 , содержащие A2007 . Очевидно, множества B1,B2,.. ,B2008 различны. Замечание. Другим примером множеств, для которых n 2008 , являются множества Ai=A {i} , где A={1, 2, ..., 2007} ( i=1, 2, ..., 2007 ).

Ответ

n=2008.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2007
Этап
Вариант 4
Класс
Класс 10
задача
Номер 07.4.10.3

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

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