Условие
При каком наименьшем 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 |
|