|
|
 |
Условие
При каком наименьшем $n$ для любого набора $A$ из $2007$ множеств найдется такой набор $B$ из $n$ множеств, что каждое множество набора $A$ является пересечением двух различных множеств набора $B$?Решение
Пусть набор $A$ содержит множества $A_1$, $A_2$, $A_{2007}$. Включим в набор множества $B_1=A_1$, $B_2=A_2$, $B_{2007}=A_{2007}$, $B_{2008} = A_1 \cup A_2 \cup \dots \cup A_{2007} \cup \{x\}$ (здесь $x$ – элемент, не принадлежащий ни одному из множеств $A_i$). Тогда все множества $B_i$ разные, и $A_i=B_{2008} \cap B_i$ для $i=1$, $2, \dots , 2007$.Далее, докажем, что для множеств $A_1=\{1\}$, $A_2=\{1, 2\}$, $A_3=\{1, 2, 3\}$, ... $A_{2007}=\{1, 2, \dots, 2007\}$ в любом наборе $B$, удовлетворяющем условию, не менее $2008$ множеств. Из условия вытекает, что для каждого $i=1$, $2, \dots 2006$ среди множеств набора $B$ найдется множество $B_i$, содержащее $A_i$, но не содержащее $A_{i+1}$ (иначе $A_i$ не может быть пересечением множеств набора $B$); заметим, что $B_i$ также содержит все множества $A_1, \dots, A_i$ и не содержит ни одного из множеств $A_{i+1}, \dots A_n$; поэтому все множества $B_i$ разные. Кроме того, среди множеств набора $B$ найдутся два множества $B_{2007}$ и $B_{2008}$, содержащие $A_2007$. Очевидно, множества $B_1$, $B_2, \dots, B_{2008}$ различны.
Замечание.
Другим примером множеств, для которых
$n \geq 2008$, являются множества
$A_i=A \setminus \{i\}$, где $A=\{1, 2, \dots, 2007\}$
($i=1$, $2, \dots, 2007$).
