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)

f(0,0) = 1/4[f(…

Each time there will be a new card on the top of the deck.

ReplyDeleteHence at some point card no. 1 is inevitable at the top.

:)

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.

DeleteExample: Consider 4 6 7 5 2 3 1 when 4 is the top card

@Taaki...

ReplyDeleteit 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 ?

induction , my friend and all is done !!

ReplyDelete@Taaki: As pointed by giridhar, your solution is not correct!!

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

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

ReplyDeleteNice problem btw

@Piyush.. Enlighten us with your solution :)

ReplyDeleteOne more induction bases solution:

ReplyDeleteInduct 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 )

@Nikhil.. Can you explain the solution?

ReplyDeleteYou 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?)

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.

ReplyDeleteIn 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.

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.

ReplyDeleteProof: 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.