Примеры на рисунках показывают, что для перекладывания $n=8$ и $n=9$ карт достаточно $s=5$ шагов (операций). Точно так же для любого $n$ достаточно $s=\left[\dfrac n2\right]+1$ шагов (т. е. $s=\dfrac{n+1}{2}$ для нечётного и $s=\dfrac n2+1$ для чётного $n$). Ниже мы докажем, что это число — наименьшее возможное.
Рисунки
Легче доказать оценку $s\ge\dfrac{n-1}{3}$, в частности, что $s\ge17$ для $n=52$ карт. Будем считать, что между соседними картами в исходном порядке 1, 2, $\ldots$, $n$ имеется «связь». Ясно, что при каждой операции разрушаются не более чем 3 связи: если мы выбираем отрезок $b$, $\ldots$, $c$ из ряда $\ldots$, $a$, $b$, $\ldots$, $c$, $d$, $\ldots$ и вставляем его между $p$ и $q$, то разрушаются связи $ab$, $cd$ и $pq$. Чтобы переложить карты в обратном порядке, нужно разрушить все $n-1$ связей. Отсюда для числа необходимых шагов $s$ получаем оценку
$$
3s\ge n-1.
$$
Чтобы получить оценку $s=\dfrac{n+1}{2}$, будем рассуждать несколько иначе. Будем считать, что между соседними картами возможны связи двух типов: „$\gt$“ или „$\lt$“ («больше» или «меньше»), и за $s$ операций все $n-1$ связи типа „$\lt$“ должны превратиться в противоположные „$\gt$“. Заметим, что на каждом шаге число связей „$\gt$“ может возрасти не более чем на 2. В самом деле, сразу 3 связи „$\lt$“ превратиться в „$\gt$“ могли бы только при переходе от $$
\ldots,a,b,\ldots,c,d,\ldots,p,q,\ldots
$$
к $$
\ldots,a,d,\ldots,p,b,\ldots,c,q,\ldots
$$
в том случае, если
$$
a\lt b,\quad c\lt d,\quad p\lt q,\quad a\gt d,\quad p\gt b,\quad c\gt q.
$$
Но эти шесть неравенств несовместимы: из них следует
$$
a\lt b\lt p\lt q\lt c\lt d\lt a
$$
— противоречие.
Далее, на первом шаге может превратиться из „$\lt$“ в „$\gt$“ лишь одна связь: ведь здесь либо $a\lt b\lt c\lt d\lt p\lt q$, либо $p\lt q\lt a\lt b\lt c\lt d$, а при этом выполняется лишь одно из трёх неравенств
$$
a\gt d,\quad
p\gt b,\quad
c\gt q.
$$
Точно так же обстоит дело и на последнем шаге, после которого получается набор из $n-1$ связей „$\gt$“ (вообще нетрудно видеть, что обратные переходы совершенно аналогичны прямым, лишь знаки „$\lt$“ и „$\gt$“ меняются ролями).
Итак, для числа $s$ необходимых шагов получаем оценку
$$
1+2(s-2)+1\ge n-1,
$$
откуда
$$
s\ge\dfrac{n+1}{2}.
$$
