Областная олимпиада по математике, 2003 год, 11 класс

Пусть $S = \{ 1,\;2, \dots ,\;n\}$. Докажите, что количество всевозможных троек множеств $(A, B, C)$ таких, что $\varnothing \subseteq A \subseteq B \subseteq C \subseteq S$ и $\left| B \right| = \frac{{\left| A \right| + \left| C \right|}}{2}$, равно $C_{2n}^n$. (Здесь $|X|$ означает количество элементов во множестве $X$, а $C_{2n}^n=\frac{(2n)!}{n!n!}$).

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

Нарисуем 4 концентрические окружности, для того чтобы визуально видеть эти множества, в самом центре окружность $A$ чуть больше $B$, еще больше $C$ и все $S$, условие $|B| = \dfrac{|A|+|C|}{2}$ запишем как $|C|-|B|=|B|-|A|$ то есть число элементов входящее в $|C|$ но не в $B$ такое же как и $B$ но не в $A$.

У нас есть $4$ зоны попадания чисел, в самом центре (в $A$) обозначим как $x_1$, только в $B = x_2$ , только $C=x_3$ и все что за ней $x_4$ где $x_3=x_4$ по ранее вышесказанному , попробуем зашифровать наши числа $S = \{ 1,\;2, \dots ,\;n\}$ символами скобок всего четыре вида, по правилу:

$()$ - если число входит в $x_1$

$(($ - входит в $x_2$

$))$ - входит в $x_3$

$)($ - входит в $x_4$

всего $n$ пар скобок, соответственно $2n$ видов скобок в ряду, где открывающие и закрывающие скобки по количеству равны $n$ в виду того что $x_2=x_3$ и проходим по каждому числу $S$ начиная с $1$ последовательно, к примеру $() \ )) \ (($ для $n=3$ значит $1$ в $x_1$, $2$ в $x_3$ и $3$ в $x_2$ то есть $A=\{1\}; \ B=\{1, \ 2\}; \ C=\{1, \ 2, \ 3\}$

Значит задача свела к подсчету количества выбрать из $2n$ скобок, ровна по $n$ скобок двух видов $( , \ )$ количество способов их переставить между собой равно $C^{n}_{2n}$