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$. Таким образом, наше соответствие — биекция.