*Consider the following one-person card game. It is played with 13 cards of
the same suit; each card is considered as having a numerical value: the ace
is 1, the deuce is 2, and so on, where the jack, queen, and king are 11, 12,
and 13, respectively. Before the game begins, the cards are shuffled. After
that the following operation is repeated. The top card of the deck is turned
up. If it is the ace, the game stops. Otherwise, the top n cards, where n is the
value of the top card, are removed from the deck and then returned there
in reverse order. An example of the game’s step is shown below:*

5 7 10 K 8 A 3 Q J 4 9 2 6 -> 8 K 10 7 5 A 3 Q J 4 9 2 6

*Does the game always stop after a finite number of iterations for every
initial state of the deck? Prove your answer.*

I’m only an amateur mathematician and this is a bit beyond my ability I think for now.

My work so far is to observe that there is probably nothing special about 13. So a smaller puzzle can be described by the following permutations, where H means “Halt”.

#### N = 4

```
(1, 2, 3, 4) H
(1, 2, 4, 3) H
(1, 3, 2, 4) H
(1, 3, 4, 2) H
(1, 4, 2, 3) H
(1, 4, 3, 2) H
(2, 1, 3, 4) (1, 2, 3, 4) H
(2, 1, 4, 3) (1, 2, 4, 3) H
(2, 3, 1, 4) (3, 2, 1, 4) (1, 2, 3, 4) H
(2, 3, 4, 1) (3, 2, 4, 1) (4, 2, 3, 1) (1, 3, 2, 4) H
(2, 4, 1, 3) (4, 2, 1, 3) (3, 1, 2, 4) (2, 1, 3, 4) (1, 2, 3, 4) H
(2, 4, 3, 1) (4, 2, 3, 1) (1, 3, 2, 4) H
(3, 1, 2, 4) (2, 1, 3, 4) (1, 2, 3, 4) H
(3, 1, 4, 2) (4, 1, 3, 2) (2, 3, 1, 4) (3, 2, 1, 4) (1, 2, 3, 4) H
(3, 2, 1, 4) (1, 2, 3, 4) H
(3, 2, 4, 1) (4, 2, 3, 1) (1, 3, 2, 4) H
(3, 4, 1, 2) (1, 4, 3, 2) H
(3, 4, 2, 1) (2, 4, 3, 1) (4, 2, 3, 1) (1, 3, 2, 4) H
(4, 1, 2, 3) (3, 2, 1, 4) (1, 2, 3, 4) H
(4, 1, 3, 2) (2, 3, 1, 4) (3, 2, 1, 4) (1, 2, 3, 4) H
(4, 2, 1, 3) (3, 1, 2, 4) (2, 1, 3, 4) (1, 2, 3, 4) H
(4, 2, 3, 1) (1, 3, 2, 4) H
(4, 3, 1, 2) (2, 1, 3, 4) (1, 2, 3, 4) H
(4, 3, 2, 1) (1, 2, 3, 4) H
```

It seems the key is to find a way to bring the 1 into the first position. One idea I had was thinking in terms of a function “distance_to_1()”.

The solutions with just one step have distance_to_1(p(0)) = p(0) -1

E.g. for (1, 2, 3, 4) H, distance_to_1(1) = 0

The same holds for two step versions:

e.g. (2, 1, 3, 4) (1, 2, 3, 4) H

distance_to_one(2) = 1

Then for 3 steps, we have something like distance_to(distance_to_1(p0)) = ??? and some kind of recursive function that eventually is guaranteed to cover all possibilities and thus prove that the solution will work for any size puzzle.. ???

That’s as far as I got going down that road.

Another idea is that there is probably some result from permutations in the group theory sense, although I know very little about this. I think it would be helpful to frame the problem in terms of composition of permutations, but I don’t know how to approach this.

Any help much apprecieated.