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

$k+1 < 2n$ болатындай натурал $n$ және $k$ сандары берілген. $a_1+a_2+\cdots+a_{2n}=0$, және барлық $i=1,2,\ldots,2n$ үшін $a_i\in\{1,-1\}$ және $a_1+a_2+\cdots+a_i\ge 0$ шарттарын қанағаттандыратын $(a_1,a_2,\ldots,a_{2n})$ тізбектер жиынын $A$ деп белгілейік. $a_k=1$ болатын $A$-ның барлық ішкі жиынын $B$ деп, ал $a_{k+1}=1$ болатын $A$-ның барлық ішкі жиынын $C$ деп белгілейік. $|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$).