Азиатско-Тихоокеанская математическая олимпиада, 2026 год

Пусть $n\ge2$ — целое число. Пусть $A_1,A_2,\ldots,A_{2^n}$ — это $2^n$ подмножеств некоторого $n$-элементного множества, расположенные в некотором порядке. Докажите, что \[ |A_1\cap A_2|+|A_2\cap A_3|+\cdots+|A_{2^n-1}\cap A_{2^n}|+|A_{2^n}\cap A_1|\ge2^{n-2}. \] (Здесь $|X|$ означает число элементов множества $X$.)

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

по формуле ключений и исключений:

$(!)|A_1\cap A_2|+...+|A_{2^n}\cap A_1|\geq 2^{n-2}$

Тоже самое что и

$(!)2(|A_1|+...+|A_{2^n}|)-2^{n-2}\geq |A_1\cup A_2|+...+|A_{2^n}\cup A_1|$

Вполне очевидно, что $|A_1|+...+|A_{2^n}|=C^{0}_n*0+...+C^{n}_n*n=2^{n-1}*n$

Поэтому

$(!)2^n*n-2^{n-2}\geq |A_1\cup A_2|+...+|A_{2^n}\cup A_1|$

Тогда заметим, что $A_i\cup A_{i+1}\leq n$.

Давайте выпишем все наши множества и будем следить за величинами $X$ и $Y$:

Если $A_i\cap A_{i+1}\geq 1$, то $+1$ к $X$, если $A_i\cup A_{i+1}\leq n-1$, то $+1$ к $Y$. Тогда заметим, что если разбить множества по парам:

$A_i$ и $\{1, 2, ..., n\} - A_i$ в паре

То так как $A_i$ соседствует с двумя подмножествами, то с одним из них оно дает $+1$ к $X$ или $Y$

Тогда, каждое множество создает хотя бы одну ситуацию где либо перечение $\geq 1$ либо объединение $\leq n-1$. Всего множеств $2^n$, значит ситуаций хотя бы $2^{n-1}$. Получается, что:

1) $Y\geq 2^{n-2}$. Тогда:

$|A_1\cup A_2|+...+|A_{2^n}\cup A_1|\leq n*(2^n-2^{n-2})+(n-1)*2^{n-2}=n*2^n-2^{n-2}$, что и требовалось доказать

2) $X\geq 2^{n-2}$. Тогда:

$|A_1\cap A_2|+...+|A_{2^n}\cap A_1|\geq 2^{n-2}$, что и требовалось доказать

усенов эльдар

ussenov eldar