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(…

What does it mean to have a non-degenerate parallelogram?

ReplyDeleteAns: 2n – 1.

ReplyDeleteProof:

Let the ith row have Ni pebbles. Let the column in which jth of these lies be denoted by Cij (1 <= j <= Ni). Now if there exist 2 rows, each of which have 2 pebbles, equal number of columns apart, we’d get a non-degenerate parallelogram.

Let’s denote the total number of pebbles by N = ∑i Ni

Consider the differences Dij = Cij - Ci1 … (2 <= j <= Ni). Thus, across all the rows, we have ∑i (Ni – 1) = N-n such differences. Now, the distinct values which a difference can have, are 1,2,..,n-1 i.e. n-1 of them. Thus, if N >= 2n, we’d have 2 (among >=n) differences which are equal (by pigeon hole :P). Note that these 2 differences are not in the same row, as per their construction. Hence, we’d have a non-degenerate parallelogram. Now, we show with an example, that N=2n-1 is possible -> just completely fill the 1st row and the 1st column.

Ans: 2n - 1

ReplyDeleteProof:

Put all the pebbles in the first row and first column i.e. 2n - 1 pebbles (as the corner square is common). With this configuration, placing a pebble anywhere on the board results in a parallelogram. Therefore, we cannot place any other pebble anywhere on the board, giving the maximum pebbles as 2n - 1.

Hey Tushar, I think proving that you cannot add pebbles to one particular configuration, only ensures that the configuration is optimal, but it need not be optimum.

Delete