Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Dec 30, 2009

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.

10 comments:

  1. 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
  2. @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. induction , my friend and all is done !!

    ReplyDelete
  4. @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. I solved it also by induction,but without proving that it should cover all permutation.

    Nice problem btw

    ReplyDelete
  6. @Piyush.. Enlighten us with your solution :)

    ReplyDelete
  7. 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. @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. 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. 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