Республиканская олимпиада по математике, 2025 год, 11 класс

Даны натуральные числа $n$ и $k$, где $k+1 < 2n$. Пусть $A$ — множество всех последовательностей $(a_1,a_2,\ldots,a_{2n})$ таких, что $a_1+a_2+\cdots+a_{2n}=0$, $a_i\in\{1,-1\}$ и $a_1+a_2+\cdots+a_i\ge 0$ для всех $i=1,2,\ldots,2n$. Пусть $B$ — подмножество всех элементов $A$, для которых $a_k=1$, а $C$ — подмножество всех элементов $A$, для которых $a_{k+1}=1$. Докажите, что $|B|\cdot |C|\ge |A|\cdot |B\cap C|$. ($|X|$ — количество элементов множества $X$.) ( Д. Елиусизов )

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

Есть очень простое решение. Каждой последовательности $(a_1, \ldots, a_{2n})$ можно поставить в соответствие правильную последовательность скобок. И так, можно посчитать $|B|$: если $a_k=1$, то ей соответствует некая закрывающая скобка, то есть $l$, что $a_l = -1$. Тогда $a_{k+1},\ldots,a_{l-1} -$ образуют правильную последовательность скобок как и $a_1, a_2, \ldots, a_{k-1}, a_{l+1}, \cdots, a_{2n}$. Тогда

$$|B|= \sum_{t=0}^{n-(k+1)/2} C_t C_{n-t-1},\; \quad |C| = \sum_{t=0}^{n-(k+2)/2} C_t C_{n-t-1}$$.

Аналогичным образом, можно посчитать $|B \cap C|$ - будут два индекса $l, t$, что $a_l = -1$, $a_t=-1$ - оба закрывающие скобки для $a_k, a_{k+1}$. Пересчитывая для всех возможных $l, t$:

$$|B \cap C| = \sum_{t=1}^{n-(k+1)/2} C_tC_{n-t-1}$$.

Справедливость неравенства проверяется напрямую используя $A.M. \geq G.M.$ в лоб (и применяя $C_n = \frac{4n-2}{n+1} C_{n-1} \leq 4$).