16-я Международная Жаутыковская олимпиада по математике, 2020 год

В множестве из 20 элементов выбраны $2k+1$ различных семиэлементных подмножеств, каждое из которых пересекается ровно с $k$ другими выбранными подмножествами. При каком наибольшем $k$ это возможно? ( А. Голованов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Ответ. при $k=2$.
Решение. Пусть $M$ — множество вычетов $\bmod {20}$. Пример для $k=2$ доставляют пять подмножеств $A_i=\{4i+1, 4i+2, 4i+3, 4i+4, 4i+5, 4i+6, 4i+7\}\subset M$, $i=0, 1, 2, 3, 4$. Пусть $k\geq 2$. Очевидно, среди любых трёх семиэлементных подмножеств есть два пересекающихся. Выберем произвольное подмножество $A$. Оно пересекается с $k$ подмножествами $B_1$, $\ldots,$ $B_k$. Остальные подмножества $C_1$, $\ldots,$ $C_k$ не пересекаются с $A$ и поэтому попарно пересекаются друг с другом. Так как каждое $C_i$ должно пересекаться с $k$ подмножествами, оно пересекается ровно с одним из подмножеств $B_j$. Все $C_i$ не могут пересекаться с одним и тем же $B_j$, так как тогда это $B_j$ пересекалось бы с $k+1$ множеством. Таким образом, найдутся два разных $C_i$, которые пересекаются с разными $B_j$; примем, что $C_1$ пересекается с $B_1$, а $C_2$ пересекается с $B_2$. Все множества, которые не пересекаются с $C_1$, попарно пересекаются друг с другом. Среди этих множеств есть $A$; следовательно, это $A$ и все $B_i$ с $i\ne 1$. Отсюда следует, что два множества $B_i$, среди которых нет $B_1$, всегда пересекаются. Аналогично рассмотрением $C_2$ получим, что два множества $B_i$, среди которых нет $B_2$, всегда пересекаются. Таким образом, в семействе $A$, $B_1$, $\ldots,$ $B_k$ есть только одна пара непересекающихся подмножеств $B_1$ и $B_2$, причём $B_1$ пересекается с $C_1$, а $B_2$ с $C_2$. В этом списке для каждого $B_i$ есть $k$ пересекающихся с ним подмножеств. Отсюда следует, что $C_i$ при $i>2$ не может пересекаться ни с одним $B_j$, а, значит, таких $C_i$ нет, то есть $k\leq 2$.