Математикадан облыстық олимпиада, 2001-2002 оқу жылы, 10 сынып

52 ойын картасының тобы берілген. Осы топтың
1) алғашқы екі орында тұрған екі карталардың орындарын алмастыруға немесе
2) бірінші орындағы картасын соңғы орынға қоюға болады.
Осы 1 және 2 операцияларды қолдану арқылы, топтағы карталарды кез келген кезекте орналастыруға болатынын дәлелдеңіздер.

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

Пронумеруем карты как $1,\dots,N$, назовем операции как $F$ и $L$.

Выберем произвольную перестановку $a_1,a_2,\dots,a_N.$

Наша алгоритм таков:

Выберем наибольшее число $k\leq N-1$ для которого за $a_k$ следует число $\neq a_{k+1}$ (считаем что первая карта следует последней). Используем $L$ пока $a_k$ не окажется первой картой. Количество карт между $a_k$ и $a_{k+1}$ ненулевое. Тогда используем $F$ и $L$ в данном порядке, $a_k$ остается первой картой но количество карт до $a_{k+1}$ уменьшится на $1$, следовательно очередно используя $F$ и $L$ в какой то момент $a_k$ стоит первой картой а $a_{k+1}$ стоит второй. Заметим что $L$ не меняет какая карта следует другой. Также заметим что так как мы выбирали $k$ наибольший, то карты $a_{k+1},\dots,a_N$ стоят в нужном нам порядке и на них не проводилась операция $F$, при этом длина нужной нам последовательности увеличилось на $1$. Значит этот алгоритм работает и в какой то момент $a_1,a_2,\dots,a_N$ следуют за друг другом, используя $L$ мы можем расставить их так что $a_k$ стоит на $k$ позиции, что требовалось.