Математикадан 52-ші халықаралық олимпиада, 2011 жыл, Амстердам

Бір бүтін $n > 0$ саны бекітілген. Бізге екі табағы бар таразы және салмақтары ${{2}^{0}}$, ${{2}^{1}}$, $\ldots$, ${{2}^{n-1}}$ болатын $n$ тас берілген. Біздің мақсатымыз — тастарды, ешбір жүрістен кейін таразының оң жақ табағы басып кетпейтіндей етіп, бір-бірлеп, $n$ жүрістің ішінде табақтарға салып шығу. Ең басында таразы табақтары бос және әрбір жүрісте біз таразыға салынбай қалған тастардың кез келген біреуін алып, оны таразының сол жақ немесе оң жақ табағына сала аламыз.
Мақсатымызды қанша әдіспен іске асыруға болатынын анықтаңдар.

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

Пусть $A_{n}$ количество таких последовательностей. Выразим $A_{n}$ через $A_{n-1}$.

Заметим, что гиря с весом $2^{n-1}$ лежит на левой чаше весов. Пусть ее положили на $k$ой. Тогда количество способов положить первые $k-1$ гирь это $C^{k-1}_{n-1}A_{k-1}$. Количество способов положить оставшиеся гири, это $2^{n-k}(n-k)!$. Тогда $A_{n}=\sum_{i=0}^n C^{i-1}_{n-1}A_{i-1}2^{n-i}(n-i)! = (2n-1)A_{n-1}$. Так как $A_{1}=1$, то $A_{n}=(2n-1)!!$.