5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Shouldn't the new deck be K184J537XA2Q6 if you invert the first four? $\endgroup$ – SirGrapefruit Jul 17 '17 at 15:36
  • $\begingroup$ @SirGrapefruit yes, you are right. Thank you for spotting it, I corrected the text! $\endgroup$ – mau Jul 17 '17 at 15:38
  • 1
    $\begingroup$ Your third sentence says, "you change the order of the first $n$ cards. I think you mean to say you "invert" them, since you mention that later, but it really isn't clear. When I first read it, I though they were randomly permuted. $\endgroup$ – GentlePurpleRain Jul 17 '17 at 15:54
  • $\begingroup$ It's an inversion $\endgroup$ – mau Jul 17 '17 at 16:14
  • 1
    $\begingroup$ I knew I have read this problem somewhere in one of my books, so I rushed to find it. Success! $\endgroup$ – William Nathanael Jul 17 '17 at 16:51
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ffao Jul 17 '17 at 17:23
  • $\begingroup$ @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? $\endgroup$ – William Nathanael Jul 17 '17 at 22:42
  • $\begingroup$ No, I can't see it. Assume the deck begins Ace, King. Then you will never find the King, ever. $\endgroup$ – ffao Jul 17 '17 at 23:50
  • $\begingroup$ @ffao If it begins with Ace, King, then we are done! It stops once it reaches Ace! $\endgroup$ – William Nathanael Jul 18 '17 at 0:18
  • $\begingroup$ And the King was never seen, which is my point. Your claim that the king will eventually be seen is false. $\endgroup$ – ffao Jul 18 '17 at 1:28
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ that's really nice! $\endgroup$ – mau Jul 18 '17 at 5:23
  • $\begingroup$ after re-reading it I have a doubt. What is the score of the deck KQJ...32A? $\endgroup$ – mau Jul 20 '17 at 17:33
  • $\begingroup$ 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$. $\endgroup$ – Mike Earnest Jul 20 '17 at 19:14
  • $\begingroup$ 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! $\endgroup$ – mau Jul 20 '17 at 19:51
  • $\begingroup$ Can you explain the last sentence further? I mean, what score makes the top card an ace? $\endgroup$ – William Nathanael Jul 21 '17 at 12:33

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.