Q21 Matemática  (IMO Shortlist 1994)

Há $n+1$ células em uma linha rotuladas de $0$ a $n$ e $n+1$ cartões rotulados de $0$ a $n$. As cartas são colocadas arbitrariamente nas células, uma por célula. O objetivo é colocar o cartão $i$ na célula $i$ para cada $i$. O movimento permitido é encontrar o menor $h$ tal que a célula $h$ tenha um cartão com um rótulo $k>h$, pegue esse cartão, deslize os cartões nas células $h+1$, $h+2$ , ... , $k$ uma célula à esquerda e colocar o cartão $k$ na célula $k$. Mostre que no máximo movimentos de $2^n-1$ são necessários para colocar todas as cartas na célula correta e que existe uma posição inicial única que requer movimentos de $2^n-1$. [Por exemplo, se $n=2$ e a posição inicial for 210, obtemos 102, depois 012, um total de 2 movimentos.]