1

Assume a deck of $50$ cards, numbered from $1$ to $50$. Look at the number of the top card, assume it is $K$. Now, reverse the order of the first $K$ cards of the deck. For example, if $K=5$ change the order of the top $5$ cards so that the fifth card becomes first, the fourth becomes second, etc. Will this process ever stop?

user642796
  • 52,188
user75013
  • 131
  • It will stop is 1 ever becomes the top card. Maybe you mean whether that will necessarily, eventually happen for any initial permutation? – Thomas Ahle Apr 29 '13 at 12:18
  • Can you think of a quantity that will always increase, or always decrease, when you do this? Is so, the process must stop. – Harald Hanche-Olsen Apr 29 '13 at 12:18

1 Answers1

2

HINT: The process stops only when $1$ comes to the top of the deck. Suppose that you knew that the process would eventually stop with a deck of only $49$ cards. Now start with your shuffled deck of $50$ cards.

  • If card $50$ is on the bottom, you’re essentially playing with just the top $49$ cards, and by hypothesis the $1$ will eventually come to the top.
  • If card $50$ is not at the bottom, but card $1$ is, pretend temporarily that card $50$ is really card $1$. Until it comes to the top you’re playing with the top $49$ cards, and since card $50$ is filling in for card $1$, by hypothesis it will eventually come to the top. At that point you’ll reverse the whole deck, bringing $1$ to the top.
  • If neither card $50$ nor card $1$ is on the bottom, you’re still essentially playing with the top $49$ cards until either the $1$ comes to the top, in which case you can stop, or the $50$ comes to the top. In the latter case you’ll reverse the deck, putting the $50$ on the bottom, and you’re in the first case.

So how could you show that the process always eventually brings the $1$ card to the top when there are only $49$ cards?

Brian M. Scott
  • 616,228
  • Hi Brian, I did not fully understand you answer, could you please provide an example or a more detailed explanation ? – user75013 Apr 29 '13 at 13:21
  • @user75013: Depending on what you know, the approach that I’m suggesting may or may not be useful, so let me ask first: are you familiar with mathematical induction? – Brian M. Scott Apr 29 '13 at 13:24
  • I'm a law student lost in the world of math with this question. I did study mathematical induction in high school, though I don't remember much. – user75013 Apr 29 '13 at 13:27
  • @user75013: Oh, dear; I sympathize. :-) Okay; the argument that I’m suggesting is an argument by induction, showing that if the process necessarily ends with a deck of $n$ cards, then it also necessarily ends with a deck of $n+1$ cards. Since it certainly always ends with a deck of $1$ card, this would imply that it ends with a finite deck of any size. My answer is an outline of the argument that if it ends with $49$ cards, then it ends with $50$. The same argument can be carried out in general, with $n+1$ replacing $50$, to show that if it ends with $n$ cards, it ends with $n+1$. ... – Brian M. Scott Apr 29 '13 at 13:30
  • ... The argument itself is in three cases. If the $50$ card is on the bottom, no move can possibly affect it: it will stay on the bottom forever, because you never reverse more than the top $49$ cards. Thus, you are in effect playing with a $49$-card deck, and by hypothesis the $1$ will eventually rise to the top. If the $1$ is on the bottom, pretend that the $50$ is the $1$ until it comes to the top, as by hypothesis it must: until it does, you’re again playing with a $49$-card deck in which the $1$ is labelled $50$. And when it does, the required move simply reverses the deck, bringing ... – Brian M. Scott Apr 29 '13 at 13:33
  • 1
    ... the $1$ to the top. The third case, in which neither the $1$ nor the $50$ is on the bottom, is similar: you never touch the bottom card unless the $50$ comes to the top, and if it does, the required move puts it on the bottom, so that you’re in the first case, which we know ends. If the $50$ doesn’t come to the top, you’re playing with a $49$-card deck in which the $50$ card represents whichever card is actually on the bottom, and by hypothesis with a $49$-card deck the $1$ will come to the top eventually. The only way for that to fail is for the $50$ to beat it to the top, which is okay. – Brian M. Scott Apr 29 '13 at 13:37
  • Hi Brian, first of all thanks for the quick response and also for the sympathy :) . I understand your answer, but (and correct me if i'm wrong) I still need to prove that the hypotheses that 1 will eventually rise to the top, or is it clear for some reason ? – user75013 Apr 29 '13 at 13:47
  • @user75013: I showed that if $1$ always rises to the top with a $49$-card deck, then it must also do so with a $50$-card deck. You need to recast that as an argument that if it always rises to the top with an $n$-card deck, then it always does so with an $(n+1)$-card deck; this is really just a matter of substituting $n$ for $49$ and $n+1$ for $50$ throughout. That argument is then the induction step of a proof by induction: you’ve shown that $P(n)$ implies $P(n+1)$ for any positive integer $n$, where $P(n)$ is the statement that $1$ eventually rises to the top of an $n$-card deck. To ... – Brian M. Scott Apr 29 '13 at 13:52
  • ... complete the proof by induction, you have to verify that it ‘gets off the ground’, i.e., that $P(1)$ is actually true — but that’s completely trivial. – Brian M. Scott Apr 29 '13 at 13:53
  • I was wondering if I could use your technique to calculate the average number of swaps that will happen before termination. However I get stuck at the point where neither 1 and 50 is the last card and 50 has just been swapped from the top to the bottom. Now can I assume that the 49 top cards will be distributed evenly? – Thomas Ahle Apr 29 '13 at 16:19
  • @Thomas: You mean uniformly random over all $49!$ possibilities? I doubt it, but that may just be pessimism speaking: I don’t have any real feel for what’s happening. My inclination would be to work out the results for $n\le 5$, say, by brute force to try to get some idea. – Brian M. Scott Apr 29 '13 at 16:30
  • @BrianM.Scott how can I prove that any one of the 49 cards will eventually get to the top of the deck? – user75013 Apr 29 '13 at 17:27
  • @user75013: It isn’t true: if the deck starts with the $1$ on top, it will never change. Are you sure that that’s what you really meant to ask? – Brian M. Scott Apr 29 '13 at 17:35
  • Hi! What I meant was for the third case - where 1 or 50 are not on top or bottom - how can I prove that 1 or will eventually get to the top of the deck? (The hypothesis) – user75013 Apr 29 '13 at 21:51
  • @user75013: I gave that argument in the last part of my first long comment. You're playing with a $49$-card deck until the $50$ turns up. If the $1$ turns up first, you're done. If not, once the $50$ turns up, it goes to the bottom, and you're in the first case. – Brian M. Scott Apr 30 '13 at 03:27
  • @BrianM.Scott: what you wrote is that the 1 will eventually go up by hypothesis-I'm talking about proving this hypothesis - how can I make sure it happens? – user75013 Apr 30 '13 at 05:07
  • @user75013: You don’t have to: that’s the induction hypothesis. You assume that $P(n)$ is true and prove that that entails the truth of $P(n+1)$. Since $P(1)$ is true, it follows that $P(n)$ is true for all $n\ge 1$: that’s the principle of mathematical induction. – Brian M. Scott Apr 30 '13 at 05:11
  • @BrianM.Scott: First of all many thanks. From what I read about mathematical induction - The proof consists of two steps: The basis (base case): showing that the statement holds when n is equal to the lowest value that n is given in the question. In my case n=1. The inductive step: showing that, with respect to each n for which the statement holds, then the statement must also hold when n + 1 is substituted for n. If I show that 1 will eventually go to the top with a deck size 4 (n) and than a deck size 5 (n+1), can this be enough for it to hold on a deck size 50 ? – user75013 Apr 30 '13 at 05:34
  • @user75013: That’s exactly right. And it then follows that it holds for all $n\ge 1$. One argument to see this is to let $B$ be the set of $n\ge 1$ for which it doesn’t hold. $B$ is a set of positive integers, so if it’s not empty, it has a smallest element $m$. Now $m$ can’t be $1$, because we know that it holds for $1$, so $m>1$. But then $m-1\ge 1$, and $m-1$ is not in $B$, so it holds for $m-1$, and the induction step proves that it also holds for $(m-1)+1=m$. This is a contradiction, so $B$ must be empty, and it therefore holds for all $n\ge 1$. – Brian M. Scott Apr 30 '13 at 05:37
  • @BrianM.Scott: Hi Brian, me again :) Need your help with Phrasing the argument/claim of the induction. what should be the claim of the induction ? for example: "For any number of cards if 1 is the largest card that comes on top , 1 eventually comes at top" – user75013 May 06 '13 at 14:56
  • @user75013: Take $P(n)$ to be the statement that if you play the game with an $n$-card deck, the $1$ eventually comes to the top. $P(1)$ is trivially true, and the argument that we discussed before gives you the induction step $P(n)\to P(n+1)$. – Brian M. Scott May 06 '13 at 14:59
  • @BrianM.Scott: have you seen this post? link – user75013 May 06 '13 at 15:14
  • @user75013: No, I hadn’t. Nikhil Garg’s induction argument also works, though it isn’t very clearly explained. Pratik Poddar’s argument uses the same basic idea as mine, though he proves a stronger statement. – Brian M. Scott May 06 '13 at 15:24
  • @BrianM.Scott: I really like your proof, the only thing that I'm having trouble with is in the third case, you assume that the 50 will go up like the 1 card does, but it wasn't proved. – user75013 May 06 '13 at 19:22
  • @user75013: Yes, it was: in the comment up near the top with the upvote. – Brian M. Scott May 06 '13 at 19:26
  • @BrianM.Scott: The thing is - If one is at the bottom, you still need to prove that the 50 card will reach to the top eventually, but you didn't. I understand that your'e playing with a deck of 49 cards (when 1 is at the bottom) but proving that 1 will eventually get to the top (by the induction hypothesis) is not the same as proving that the 50 card will get to the top eventually. – user75013 May 06 '13 at 21:15
  • @user75013: Yes, I did: that’s the whole point of ‘pretend that the $50$ is the $1$ until it comes to the top’. Just imagine that the $50$ card temporarily bears the alias $1$. Then the top $49$ cards are labelled $1$-$49$, and by hypothesis the (pseudo-)$1$ will eventually come to the top. Now it takes off its disguise, resumes its proper identity as $50$, and you invert the deck. – Brian M. Scott May 07 '13 at 13:37