There are
![n + 1](/media/m/3/6/d/36dc98984132471cc8b030d766fd893a.png)
cells in a row labeled from
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
to
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
and
![n + 1](/media/m/3/6/d/36dc98984132471cc8b030d766fd893a.png)
cards labeled from
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
to
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
. The cards are arbitrarily placed in the cells, one per cell. The objective is to get card
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
into cell
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
for each
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
. The allowed move is to find the smallest
![h](/media/m/e/4/3/e438ac862510e579cf5cbdbe5904d4ba.png)
such that cell
![h](/media/m/e/4/3/e438ac862510e579cf5cbdbe5904d4ba.png)
has a card with a label
![k > h](/media/m/5/c/c/5cce0e7a73eed4c5a5b3987f8a5425ef.png)
, pick up that card, slide the cards in cells
![h + 1](/media/m/e/7/f/e7f1af3edc2ea55026105b56e80e1f7d.png)
,
![h + 2](/media/m/1/4/6/146c28f0100d356e6ef6397f65a5c639.png)
, ... ,
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
one cell to the left and to place card
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
in cell
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
. Show that at most
![2^n - 1](/media/m/3/6/8/368d10e8ec7984984aeaca1729252368.png)
moves are required to get every card into the correct cell and that there is a unique starting position which requires
![2^n - 1](/media/m/3/6/8/368d10e8ec7984984aeaca1729252368.png)
moves. [For example, if $n = 2$ and the initial position is 210, then we get 102, then 012, a total of 2 moves.]
%V0
There are $n + 1$ cells in a row labeled from $0$ to $n$ and $n + 1$ cards labeled from $0$ to $n$. The cards are arbitrarily placed in the cells, one per cell. The objective is to get card $i$ into cell $i$ for each $i$. The allowed move is to find the smallest $h$ such that cell $h$ has a card with a label $k > h$, pick up that card, slide the cards in cells $h + 1$, $h + 2$, ... , $k$ one cell to the left and to place card $k$ in cell $k$. Show that at most $2^n - 1$ moves are required to get every card into the correct cell and that there is a unique starting position which requires $2^n - 1$ moves. [For example, if $n = 2$ and the initial position is 210, then we get 102, then 012, a total of 2 moves.]