Interesting Riddle about a Game with Playing Cards

Question

Let me list the game and then I will pose my question.

A game called finding Ace is described as follows. Given a pack of 13 cards of the same suit picked from a shuffled deck, we are going to find the Ace in the following way. Let the left most end be the top. If the card on the top is 1 (i.e., Ace), then the game is over. Otherwise, check the number on the top card, say n, then remove the first n cards from the pack and put them back in the reverse order. Repeat the process until Ace surfaces to the top.

Example:

D7 D13 D10 D4 D5 D1 D6 D2 D12 D11 D9 D3 D8

D6 D1 D5 D4 D10 D13 D7 D2 D12 D11 D9 D3 D8

D13 D10 D4 D5 D1 D6 D7 D2 D12 D11 D9 D3 D8

D8 D3 D9 D11 D12 D2 D7 D6 D1 D5 D4 D10 D13

D6 D7 D2 D12 D11 D9 D3 D8 D1 D5 D4 D10 D13

D9 D11 D12 D2 D7 D6 D3 D8 D1 D5 D4 D10 D13

D1 D8 D3 D6 D7 D2 D12 D11 D9 D5 D4 D10 D13

Reverse 6 times.

My question: What is the absolute maximum number of reverses it would take to move the ace to the top?

I wrote a program that would play this game and then ran it a billion times to see the results.

The highest number of reverses the program found was 79.

I am going to edit my code to list the original arrangement of the game that takes the most reverses, I just have not gotten around to it. Maybe that will give a clue as to if there is an arrangement that would take more reverses than 79.

I know this may not be the actual maximum because there are over 6 billion arrangements possible, while I have checked less than a billion.

Hopefully someone has a simple solution to compute the most reverses needed.

Thanks all!

Answer 1

I'm not able to do a proof of the maximum number of reverse operations but ...

Try:

2 9 4 5 11 12 10 1 8 13 3 6 7

After reversing 8o times it will be

1 2 3 4 5 6 7 8 9 10 11 12 13

@Michael listed the solutions from 2 to 10 (https://math.stackexchange.com/a/2650497/315401). Below is a few more solutions.

11 cards: 51 steps $( 4, 9, 11, 6, 10, 7, 8, 2, 1, 3, 5 )$

12 cards: 65 steps $(2, 6, 1, 10, 11, 8, 12, 3, 4, 7, 9, 5)$

13 cards: 80 steps $(2, 9, 4, 5, 11, 12, 10, 1, 8, 13, 3, 6, 7)$

Answer 2

It will always end. By induction on $n$.
Let $P$ be a permutation of $\{1,2,...,n\}$.
Suppose the last card is $m$. If $m=n$ then that card is irrelevant; the game only involves the front $n-1$ cards, and by induction that terminates.
If $m\ne n$, let $Q$ be the permutation formed by swapping cards $m$ and $n$. So the last card of $Q$ is $n$.
If $m$ ever reaches the front for $Q$, then $n$ would reach the front for $P$; $n$ then goes to the back; and we are reduced to the front $n-1$ cards.
If $m$ never reaches the front for $Q$, then neither $m$ nor $n$ reaches the front for $Q$, so the same holds for $P$, and the number of reverses for $P$ equals the number of reverses for $Q$.

Here are the maximum results for shorter suits:

2 cards: 1 step, $(2,1)$
3 cards: 2 steps,$(3,1,2),(2,3,1)$
4 cards: 4 steps, $(3 , 1 , 4 , 2) ,(2 , 4 , 1 , 3)$
5 cards: 7 steps, $(3 , 1 , 4 , 5 , 2)$
6 cards: 10 steps, $(5, 6, 4, 1, 3, 2 ), (4 ,5 , 6 , 2, 1, 3 ), (4, 1, 6 , 5 , 2 , 3 ), (4, 1, 5 , 2 , 6 , 3), (3 , 6 , 5 , 1 , 4 , 2) $
7 cards, 16 steps $(4 , 7 , 6 , 2 , 1 , 5 , 3 ),(3 , 1, 4 , 6 , 7 , 5, 2 )$
8 cards, 22 steps $(6 , 1 , 5 , 7 , 8 , 3 , 2 , 4 )$
9 cards, 30 steps $(6 , 1 , 5 , 9 , 7 ,2, 8 , 3 , 4 )$
10 cards, 38 steps $(5, 9, 1, 8, 6 , 2, 10, 4 , 7 , 3 )$