комбинаторный дизайн с ограничениями на чётность

[maxal]

Пусть $S$ - семейство непустых подмножеств множества $N=\{1,2,\dots,n\}$ такое, что $|S|$ нечётно, каждый элемент $N$ появляется в $S$ чётное число раз, и каждая пара элементов $N$ появляется в элементах $S$ чётное число раз.

Докажите, что найдётся такая пара множеств $s_1,s_2\in S$, что $\min s_1 < \min s_2$ и $\max s_1 > \max s_2$.

[gris]

Можно попробовать? Из соображений чётности следует, что каждый элемент и каждая пара присутствуют в каком-то подмножестве и не присутствуют в каком-то подмножестве. Хотя, вдруг ноль чётное число? Может быть, это и не страшно. И то, что могут быть два одинаковых подмножества.
Тогда можно безболезненно выкинуть из каждого подмножества все элементы, кроме крайних. В каждом множестве останется либо два элемента, либо один. Если единственный элемент равен $1$ или $n$, то это подмножество не может входить в решение; если не равен, то оно поставляет очевидное решение. То есть одноэлементные подмножества можно безболезненно игнорировать.
Вот теперь надо отыскать два подмножества, "строго вложенных" друг в друга. В общем, надо доказать, что существует подмножество, не содержащее ни $1$, ни $n$. У меня всё это дело визуализируется при помощи индикаторной матрицы. Этот первомай не даёт сосредоточится (Мне кажется, что это просто от противного?)

[maxal]

gris в сообщении #1390607 писал(а):

Тогда можно безболезненно выкинуть из каждого подмножества все элементы, кроме крайних.

Это неверно. Можно выкинуть все элементы, которые не являются крайними ни в каком из множеств. Но если элемент некрайний в одном множестве, но крайний в другом, то его вообще говоря нельзя выкинуть без нарушения чётности вхождений его и пар с ним.
И да, ноль - это чётное число.

[gris]

Я вчера увидел задачу и вначале понял так, что ноль не считается. Но тогда бы было слишком просто. Я подумал, что есть какой-то ещё подвох и решил подождать.
Мне кажется, что можно проигнорировать ноль у отдельных элементов. Просто выкинуть их и переименовать. Ведь на $n$ нет ограничений.

[Geen]

Наверное я что-то не понимаю, но $S=\{\varnothing\}$ удовлетворяет условию?

[maxal]

gris, у элементов - да, ноль не существеннен; но для пар - он вполне играет роль.

Geen, слово "непустых" было пропущено в условии. Кроме того, для пустого множества, непонятно как определять $\min$ и $\max$.

[waxtep]

Непонятно, как подступиться. Можно начать с существования: для $n\geqslant3$ множество всех подмножеств $N$ (кроме пустого подмножества) как раз дает нужный результат: $|S|=2^n-1$, каждый элемент встречается $2^{n-1}$ раз, а каждая пара элементов - $2^{n-2}$ раза. Для $n=3$ это единственный вариант, для бОльших $n$ можно фигурным вырезанием сделать и меньшее множество, удовлетворяющее условиям. Да, видимо, вместо семейства $S$ достаточно рассматривать множество $S$, т.к. добавление какого-либо элемента четное число раз не меняет картину четности.
Теперь пусть $a$ - минимальное из чисел, встречающееся в элементах $S$, $c$ - максимальное. Если удастся доказать, что в $S$ должно входить множество, содержащее и $a$ и $c$, то дальше легко:
1. Для какого-то $a<b<c$ в $S$ должны входить два множества, содержащих $a$ и $c$, ровно одно из которых содержит $b$: $\{a,\ldots,c\}$ и $\{a,\ldots,b\ldots,c\}$
2. Но тогда в $S$ должны быть и множества $\{a,\ldots,b,\ldots\}$ и $\{\ldots,b,\ldots,c\}$ (не содержащие $c$ и $a$, соответственно
3. А тогда и множества $\{a,\ldots\},\{\ldots,b,\ldots\},\{\ldots,c\}$ (содержащие ровно одно из трех чисел каждое). Среднее из них, $\{\ldots,b,\ldots\}$ "входит" в постулированное $\{a,\ldots,c\}$. Но вот его обязательное вхождение в $S$ надо доказать, у меня пока не получилось

[waxtep]

waxtep в сообщении #1390813 писал(а):

Но вот его обязательное вхождение в $S$ надо доказать, у меня пока не получилось

мда, а это совершенно необязательно: например, для $n=9$, можно рассмотреть множество $S$ из $3\times7=21$ элемента, где каждые $7$ элементов представляют из себя "полный комплект" для $(1,2,3), (4,5,6), (7,8,9)$

[maxal]

Видимо, пора давать подсказку: утверждение задачи неверно, постройте контрпример.