# Turn of a friendly card

You have a deck with the 13 cards of diamonds. After shuffling the deck, you will turn the first card and note its value $$n$$ (as usual A=1, J=11, Q=12, K=13). At that point, you invert the order of the first $$n$$ cards; if for example the order of the deck is 481KJ537XA2Q6, four cards are to be inverted, and the deck will then be K184J537XA2Q6. Look at the new top card and keep performing the same operation until the first card will be an ace; at that point there's nothing to do, and the operations end. Could the operations go forever?

P.S : This question has also been discussed here

• I knew I have read this problem somewhere in one of my books, so I rushed to find it. Success! Jul 17, 2017 at 16:51

An interesting fact to note is that

even with any number of cards, numbered 1 to n, the operation will terminate.

The formal proof:

Let fi be the value of the topmost card after i steps, i = 1, 2, etc. We wish to show that fm = 1 (and consequently, fj = 1 for every j > m )

Since 1 ≤ fi ≤ n, the number L1 := max{fi : i ≥1} exists.

Define t1 := min{t : ft = L1} or, in other words, t1 is the first step at which the 1st card equals to L1. In the main question, L1 equals to 13.

We claim that if t > t1, then ft < L1. To see this, note that ft cannot be greater than L1, by definition of L1. To see that ft cannot be equal to L1, we argue by contradiction. Let t be the first step after t1 such that ft = L1. At step t1, the first L1 cards were reversed, placing the value L1 at the L1 th place. For all steps s after t1 and t, we have fs < L1, which means that the card with value L1 at the L1 th place was not moved. Hence at step t, it is impossible for ft = L1, since that means that the 1st and the L1 th are the same (unless L1 = 1, in which case we are done). This contradiction establishes the claim.

Now we define two sequences. For r = 2, 3, etc. define Lr := max {fi: i > tr-1} and tr := min{t > tr-1 : ft = Lr}. As above, we assert that as long as Lr > 1, it t < tr, then ft < Lr (for each r ≥1)

Therefore, the sequence L1, L2, L3, etc. is strictly decreasing, hence one of the Lr will equal to 1, so eventually, fm = 1 for some m.

TL;DR for non-mathematicians

If the bottom card is the King, we do our operations as if there are only 12 cards. Otherwise, inspect the topmost card. The King will eventually go there, and then it will go to the bottom and never move again. Rinse and repeat until it is 1.

Credits to: "The Art of and Craft of Problem Solving" - Paul Zeitz, page 104

• I think you misunderstood the proof. The king will not necessarily eventually go to the top (in other words, L1 is not necessarily 13). What the proof is saying is that, if the King goes to the top, it will never return there.
– ffao
Jul 17, 2017 at 17:23
• @ffao Think about it like this. Assume that the King is initially on position g1. Now, where is the card g1? If it is the topmost card (aka position 1) it will make the King go up immediately. If not, it is on position g2, in which we are interested in the card g2. In other words, in the first 12 turns, if you can't find the King yet, you will find it next, because if the biggest card hasn't appeared yet, there will be no card appearing twice on the top. Can you see it? Jul 17, 2017 at 22:42
• No, I can't see it. Assume the deck begins Ace, King. Then you will never find the King, ever.
– ffao
Jul 17, 2017 at 23:50
• @ffao If it begins with Ace, King, then we are done! It stops once it reaches Ace! Jul 18, 2017 at 0:18
• And the King was never seen, which is my point. Your claim that the king will eventually be seen is false.
– ffao
Jul 18, 2017 at 1:28

A different proof:

Define the score of an deck by adding up the numbers 2k for each card k = 1,2,...,13 which is currently k places from the top. For example, when the order is A23...JQK, the score is 2 + 4 + ... + 213.

When the top card is $t$, and is not an ace, then all the places below $t$ will be unaffected, the $t$ place will become correct, while the places above $t$ will change somehow. Therefore, the score increases by $2^t$, and decreases by at most $2^1+2^2+\dots+2^{t-1}=2^t-2$, so the score increases by at least $2$ each time.

Since the score can't increase forever, the top card must become an ace at some point.

• that's really nice!
– mau
Jul 18, 2017 at 5:23
• after re-reading it I have a doubt. What is the score of the deck KQJ...32A?
– mau
Jul 20, 2017 at 17:33
• The 7 is seven places from the top, and no other card $k$ is $k$ places from the top, so the score is $2^7$. Jul 20, 2017 at 19:14
• Ok, so only cards "in their correct order" count against the score. Now it's clear - and the rationale beneath the definition for the score is clear too. Thanks again!
– mau
Jul 20, 2017 at 19:51
• Can you explain the last sentence further? I mean, what score makes the top card an ace? Jul 21, 2017 at 12:33