Задача 111772

Темы:    [ Объединение, пересечение и разность множеств ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 4+ Классы: 9,10,11

Условие

Авторы: Богданов И.И., Челноков Г.Р.

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

Решение

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

Ответ

n=2008.

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

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