Top Card

Source: Asked to me by Nikhil Garg (Sophomore, IIT Delhi)

Problem:
We have a deck of n cards with cards labeled from 1 to n. Starting at any configuration , we repeat this : If the top card has number k , we reverse the order of top k cards. Prove eventually that 1 would be the top card.

I was able to solve it. Very interesting problem. :D

Update (03/01/10):
Solution: Posted by me in the comments!! Thanx to Giridhar and KP Ashwin (CSE, IITB) for the help.

Comments

  1. Taaki...11:28 PM, December 31, 2009

    Each time there will be a new card on the top of the deck.
    Hence at some point card no. 1 is inevitable at the top.
    :)

    ReplyDelete
    Replies
    1. youwanttobefooled6:24 AM, March 04, 2018

      Hi. No it's not necessarily correct. There are cases that same number can appear multiple times on the top before card number 1 appears.
      Example: Consider 4 6 7 5 2 3 1 when 4 is the top card

      Delete
  2. Giridhar11:10 AM, January 01, 2010

    @Taaki...
    it is not true that a new card appears on the top with every reversal.
    For example : 3, 5, 4, 2, 1
    3 appears twice on top.

    If we are able to show that each reversal results in a new permutation, then we can say it is inevitable( as there are only finite permutations possible ).
    @Pratik Is this ur strategy ?

    ReplyDelete
  3. kp3:13 PM, January 02, 2010

    induction , my friend and all is done !!

    ReplyDelete
  4. Pratik Poddar7:50 PM, January 03, 2010

    @Taaki: As pointed by giridhar, your solution is not correct!!
    @Giridhar: Yes that is my strategy. Thank You.
    @KP: dude.. explanation. You thing all is well, but its not until you write it :P. BTW, Thanx. :) I was not able to find a "cool" solution until I saw your comment!

    Solution:
    We can prove that each operation results in a completely new permutation.
    This can be proved by induction.

    This is of course true for base case k=2

    Assume its true for k=n-1, i.e if there are n-1 numbers, then each operation results in a new permutation. To prove that this is true for k=n.

    When there are n numbers, say the number at the bottom of the stack is n'. Now, we have 1 to n numbers excluding the number n' in the first n-1 numbers. Now each operation would result in a new permutation of n-1 numbers by the induction hypothesis. Until the number n comes to the top. Now the stack is inverted and n can never come to the top again. So, we are left the n-1 numbers again and each operation would result in a new permutation. Note the the two set of permutations are disjoint as in the first case, n' is always at the end. In the second case, n is always at the end.

    So, each operation results in a new permutation. Since there are only n! (finite) permutation possible out of which (n-1)! (>=1) are "win" permutations, we will always reach a state when 1 is at the top.

    Hope that is clear! Thanx Nikhil for the problem and Giridhar, KP for the hint.

    ReplyDelete
  5. Piyush8:41 PM, January 03, 2010

    I solved it also by induction,but without proving that it should cover all permutation.

    Nice problem btw

    ReplyDelete
  6. Pratik Poddar8:43 PM, January 03, 2010

    @Piyush.. Enlighten us with your solution :)

    ReplyDelete
  7. NG10:54 PM, January 03, 2010

    One more induction bases solution:

    Induct on the largest card that can come on top.

    Base case: For any number of cards if 1 is the largest card that comes on top , 1 eventually comes at top ( as if !! )

    IH : If Largest card that can come at top after any finite number of moves is less then n , We reach 1 at top in finite number of moves.

    Proof: Assume it does not hold. Then this process does not terminate. Of all the possible cards at top , say n is the largest. After this step , n goes at bottom , and never is replaced again- no card greater then n comes at top ever. So by IH we take only finite moves from now onwards to get to 1 at top.


    ( I know it is little weird n extended )

    ReplyDelete
  8. Pratik Poddar7:33 PM, January 04, 2010

    @Nikhil.. Can you explain the solution?

    You seem to have mixed induction on number of cards and induction on the largest card on top. Define what n is in your induction hypothesis. What is the number of cards in the induction statement? (isn't it n?)

    ReplyDelete
  9. NG8:59 PM, January 05, 2010

    No . n is the largest number which comes at top. I am not even keeping a track of the number of cards in deck- that can be anything , I dont even want cards to be continuous in numbering or all cards to have finitely large numbers. I am just concerned with the largest card that comes on top.

    In the original problem , since the cards are from 1 to n, so largest card that comes at top is bound , so my proof establishes the desired there.

    ReplyDelete
  10. Ashutosh4:41 PM, July 06, 2011

    Claim 1: if in the initial pile the largest number is not at the last location then after a finite number of reversals it will be.

    Proof: Lets say N is the number of cards, Nth card is the largest. Lets say, ith card is on top. After 1st shuffling, i will be at the ith location in the deck. If N is not at the Nth location, then it will come at the top in one of 1-(N-1) reversals, and then it will settle at the bottom.

    The same will continue for N-1 and so on. Eventually the whole deck should be sorted with 1 at the top.

    ReplyDelete
  11. Pratik Poddar1:08 PM, September 08, 2026

    Fair - with the induction stated on "the largest value that ever reaches the top", the proof goes through and the deck size is irrelevant. That is essentially the clean termination argument: once that largest card is reversed into its own position it can never return to the top, and you induct downward. (replied using AI)

    ReplyDelete
  12. Pratik Poddar1:08 PM, September 08, 2026

    The conclusion is right but the middle step needs more justification - the top card value does not simply walk upward toward N (see the counterexample in the next comment on this post: top values can repeat). The watertight version: suppose, for contradiction, the process never puts 1 on top. Finitely many permutations + deterministic moves force a cycle. Let m be the largest card that ever appears on top during that cycle. When m is on top, the reversal moves it to position m. For m to reach the top again, some reversal must bring the card at position m to the top - i.e. the top card must equal m - impossible while m sits at position m, and no larger card ever comes to the top. Contradiction. So 1 eventually reaches the top. (replied using AI)

    ReplyDelete
  13. Pratik Poddar1:12 PM, September 08, 2026

    Correct - nice example. 4 6 7 5 2 3 1 gives top sequence 4, 5, 2, 4, ... so the top value really can repeat. Any proof that relies on the top card strictly increasing (or never repeating) is broken; the argument has to run through the "largest card that ever reaches the top gets frozen at its position" idea instead. (replied using AI)

    ReplyDelete

Post a Comment

Popular posts from this blog

Lion and Man in a Circular Cage: Can the Lion Catch the Tamer?

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...
Read more

Expected Tosses for Consecutive Heads: 2 Heads vs 3 Heads Puzzle

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more

Polya's Urn Problem: Expected Balls in the Smaller Urn

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...
Read more