3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I would suggest revising your program to take a variable number of cards, to try the orders systematically, and print out a number of the longest games for each number of cards. Start with just a few cards and look at the results. You may see a structure to the long runs that you can prove must always apply. $\endgroup$ – Ross Millikan Feb 12 '18 at 16:45
  • $\begingroup$ In searching for longest run, of course you can skip all starting positions with $1$ on the top. You can skip all starting positions with the highest number on the bottom as you will never see it. You can also skip all starting positions with the highest number on the top, as the first move will put it on the bottom and you will never see it again, so that will just add one move to the longest run with one card less. "Obviously" you can do better. $\endgroup$ – Ross Millikan Feb 12 '18 at 16:49
  • $\begingroup$ @RossMillikan there are positions with the highest card on top which is not the result of applying a step to any previous position. I don't think you can categorically rule those out as the longest. Of course, the longest probably won't have the largest card on the top, but I think you should be cautions. $\endgroup$ – Arthur Feb 12 '18 at 17:09
  • $\begingroup$ That is true, but I am pretty sure the number of steps grows faster than the number of cards. Starting with the largest card on top can only add one to the length. I am trying to figure out how to get permutations out of itertools in Python to code this. $\endgroup$ – Ross Millikan Feb 12 '18 at 17:23
  • $\begingroup$ I have started messing with my code. I was able to code the permutations of an array, now I just need to implement that into my original program. I will have it run through every iteration of one suit of cards, then play the game, and then print the maximum reverses as well as that starting arrangement. Hopefully I will be able to finish it up tonight. $\endgroup$ – Tyler Feb 12 '18 at 22:13
1
$\begingroup$

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 )$

$\endgroup$
1
$\begingroup$

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)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.