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

Дана колода из 52 карт над которыми разрешается проводить следующие операции:
а) менять местами первые две карты;
б) переставлять первую карту на последнее место.
Докажите, что используя эти операции можно расставить карты в произвольном порядке.

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

Пронумеруем карты как $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$ позиции, что требовалось.