11-я Международная Жаутыковская олимпиада, 2015 год

Обозначим через $A_n$ множество разбиений последовательности $1, 2, \dots, n$ на несколько подпоследовательностей, в каждой из которых любые два соседних члена имеют разную чётность, а через $B_n$ — множество разбиений последовательности $1, 2, \dots, n$ на несколько подпоследовательностей, в каждой из которых все члены имеют одинаковую чётность (например, разбиение $\{(1, 4, 5, 8), (2, 3), (6, 9), (7)\}$ является элементом $A_9$, а разбиение $\{(1, 3, 5), (2, 4), (6)\}$ является элементом $B_6$).
Докажите, что при каждом натуральном $n$ множества $A_n$ и $B_{n+1}$ содержат одинаковое количество элементов. ( Д. Елиусизов )

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

Комментарии от администратора Комментарии от администратора №1.     Для доказательства равенства $|A_n|=|B_{n+1}|$ мы построим биекцию между двумя видами разбиений.
Пусть $A$ — разбиение первого вида, то есть в каждой подпоследовательности, входящей в $A$, чётности членов чередуются. Мы сопоставим этому разбиению разбиение $B$, заданное следующим правилом: Два числа $x < y$ — соседние в некоторой подпоследовательности из $A$ тогда и только тогда, когда $x$ и $y+1$ — соседние в некоторой подпоследовательности из $B$.
Например, разбиению $\{(1, 4, 7, 8), (2, 5, 10), (3,6), (9)\}\in A_{10}$ соответствует $\{(1, 5, 11), (2, 6), (4, 8),(3, 7, 9), (10)\} \in B_{11}$. Из этого правила немедленно следует, что в каждой подпоследовательности из $B$ все члены имеют одинаковую чётность, то есть $B\in B_{n+1}$. Сопоставляя каждой паре $(x, z)$ соседних членов подпоследовательности в любом разбиении $B\in B_{n+1}$ пару $(x, z-1)$ (в которой, очевидно, $x < z-1$ и числа $x$ и $z-1$ одной чётности), мы получим единственное разбиение $A\in A_n$, переходящее в $B$. Таким образом, наше соответствие — биекция.