MathDB

There are n \plus{} 1 cells in a row labeled from

0

n

and n \plus{} 1 cards labeled from

0

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 \plus{} 1, h \plus{} 2, ... ,

k

one cell to the left and to place card

k

in cell

k

. Show that at most 2^n \minus{} 1 moves are required to get every card into the correct cell and that there is a unique starting position which requires 2^n \minus{} 1 moves. [For example, if n \equal{} 2 and the initial position is 210, then we get 102, then 012, a total of 2 moves.]

Problem Statement