Topswaps Puzzle Termination Proof

Question

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.

Answer 1

Suppose the game never ends.

1. If K is at the bottom, then we can remove that card, since it will never move anymore.

2. If K is not at the bottom but eventually gets to the top, then it becomes flipped to the bottom, go to case 1.

3. If K is not at the bottom but never gets to the top, then it really doesn't matter what number K represents: the number is only used when it gets to the top. So we can just replace K with a blank card, and it won't make a difference. Also, since K is never used, the last card will never be touched, since no operation can touch the 13th card except when K gets to the top. Therefore we can similarly replace that with a blank card.

   Now since whatever is written on the blank cards doesn't matter. Why not write K on the last card, and write the number of the last card on K? It won't affect the game in any way.

   After we re-write the two cards, the deck is now 12 shuffled cards plus a K at the bottom. Now remove K as in the first case.

There is 12 cards only now. We repeat the process. Eventually the Ace will be at the top.

Answer 2

If you don't get to $1$ on the top you must enter a loop because there are only finitely many orders of the cards. Assume there is a loop. Let $k$ be the largest number you see in the loop. When you see $k$ and reverse the top $k$ cards, card $k$ will be in position $k$. No card that you see is large enough to move card $k$ from where it is, so there cannot be a loop. Hence the game must terminate.