Medium | Probability |

A chess tournament has K levels and 2^K players with skills 1 > 2 > ... >2^K. At each level, random pairs are formed and one person from each pair proceeds to next level. When two opponents play, the one with better skills always wins. What is the probability that players 1 and 2 will meet in the final level?

Hint

Consider K=1 (2 players), the probability is 1.

Consider K=2 (4 players); first round can be in following ways:

1-2 | 3-4

1-3 | 2-4

1-4 | 2-3

They don't meet in finals in first case (of 3). Thus, for K=2, the probability that they meet is 2/3.

I assure you that this probability gets close to 1/2 for large K. Just notice that if 1 and 2 meet before final, they dont meet at final.

Consider K=2 (4 players); first round can be in following ways:

1-2 | 3-4

1-3 | 2-4

1-4 | 2-3

They don't meet in finals in first case (of 3). Thus, for K=2, the probability that they meet is 2/3.

I assure you that this probability gets close to 1/2 for large K. Just notice that if 1 and 2 meet before final, they dont meet at final.

Answer

N/2(N-1)

Solution

If you worked out conditional probability, that is fine. Here we present the combinatorial solution. Imagine the levels proceed in any random way such that player X and Y appear for final level. This can be imagined as N players getting partitioned into two groups of N/2 players each, with player X topping in first group and player Y in second. The best player of each partition reaches final. We only need to ensure that above partition separates player 1 from 2. The probability that a random partition separates 1 & 2 is (N/2) / (N-1) (how?)

Here is how: for creating a partition to separate them, we pick (N/2) people from N, wishing to take player 1, but not player 2.

Here is how: for creating a partition to separate them, we pick (N/2) people from N, wishing to take player 1, but not player 2.

Medium | Probability |

A coin is tossed 10 times and the output written as a string. What is the expected number of HH? Note that in HHH, number of HH = 2. (eg: expected number of HH in 2 tosses is 0.25, 3 tosses is 0.5)

Hint

Recursion

Solution

Let the expected number of HH for n tossed is E(n). So, probability that an (n-1) toss experiments, ends in T is 1/2.

So, E(n) = 1/2*E(n-1) + 1/2*( 1/2*(E(n-1)+1) + 1/2*(E(n-1)))

(The first case when it ends in T. & The second case when it ends in H.

In the second case, if you get an H then, you get 1 more HH. )

So, E(n) = E(n-1) + 1/4, us E(2) = 1/4

So, E(n) = (n-1)/4

For n=10, E(10) = 2.25

So, E(n) = 1/2*E(n-1) + 1/2*( 1/2*(E(n-1)+1) + 1/2*(E(n-1)))

(The first case when it ends in T. & The second case when it ends in H.

In the second case, if you get an H then, you get 1 more HH. )

So, E(n) = E(n-1) + 1/4, us E(2) = 1/4

So, E(n) = (n-1)/4

For n=10, E(10) = 2.25

Source: Placement Test

Enable Like and Comment Medium | Probability |

The stick drops and breaks at a random point distributed uniformly across the length. What is the expected length of the smaller part?

Solution

The probability that the break point belongs to first half is 1/2. In this case, the expected length of the small part is L/4. Its L/4 in the other case too. Hence E = 1/2*L/4 + 1/2*L/4 = L/4

Source: Quant Interview

Enable Like and Comment Hard | Probability |

There are 26 black(B) and 26 red(R) cards in a standard deck. A run is number of blocks of consecutive cards of the same color. For example, a sequence RRRRBBBRBRB of only 11 cards has 6 runs; namely, RRRR, BBB, R, B, R, B. Find the expected number of runs in a shuffled deck of cards.

Hint

Linearity of expectation

Answer

27

Solution

We form the answer for general deck of 2n cards, with n red cards and n black cards. Consider any sequence X1,X2..X2n (of R & B). Now define Y1 = 1;

Yi = 1 if Xi and X(i-1) are of different colors

Yi = 0 otherwise.

We want to find E[Y1 + ..+ Y2n], using linearity of expectation, = E(Y1) +...+E(Yn). Now note that, E[Y1] = 1 and E[Yi] = E[Yj] for the rest (by symmetry)

Also E[Yi] = E(Y2) = P(X2 is diff from X1) = (number of ways first two are RB or BR) / (Total number of orientations) = 2 * [ (2n-2)choose(n-1) ] / [ 2n choose n ] = n/(2n-1)

Ans = 1+(2n-1)*E[Y_i] = n+1

This is 27 for deck of 52 cards.

Yi = 1 if Xi and X(i-1) are of different colors

Yi = 0 otherwise.

We want to find E[Y1 + ..+ Y2n], using linearity of expectation, = E(Y1) +...+E(Yn). Now note that, E[Y1] = 1 and E[Yi] = E[Yj] for the rest (by symmetry)

Also E[Yi] = E(Y2) = P(X2 is diff from X1) = (number of ways first two are RB or BR) / (Total number of orientations) = 2 * [ (2n-2)choose(n-1) ] / [ 2n choose n ] = n/(2n-1)

Ans = 1+(2n-1)*E[Y_i] = n+1

This is 27 for deck of 52 cards.

Source: Quantnet

Enable Like and Comment Hard | Probability |

An ant is standing on one corner of a cube & can only walk on the edges. The ant is drunk and from any corner, it moves randomly by choosing any edge! What is the expected number of edges the ant travels, to reach the opposite corner?

Hint

Try to find the equivalent vertices with respect to distance yet to travel. This should give 4 equivalent merged vertices, with 1st being start & 4th being destination.

Solution

Let the expected number of step required to go from (0,0,0) to (1,1,1) be E0.Also let expected number of step required to reach (1,1,1) from (0,0,1)(Or from (0,1,0) or from (1,0,0)) be E1. similarly expected number of step required to reach (1,1,1) from (0,1,1) (Or from (1,0,1) or from (1,1,0)) be E2.Then we can write:

E0=1/3(E1+E1+E1)+1

E1= 1/3*E0 + 2/3*E2 + 1

E2 = 2/3*E1 + 1

solving this we find E0 as 10.

E0=1/3(E1+E1+E1)+1

E1= 1/3*E0 + 2/3*E2 + 1

E2 = 2/3*E1 + 1

solving this we find E0 as 10.

Source: Quant Interview

Enable Like and Comment Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |