TIFR CSE 2022 | Part A | Question: 7

Question

Initially, $N$ white beads are arranged in a circle. A number $k$ is chosen uniformly at random from $\{1, \ldots, N-1\}$. Then a set of $k$ beads is chosen uniformly from the white beads, and these $k$ beads are coloured black. The position of the beads remains unchanged. What is the probability that the black beads occur sequentially in the circle, i.e., at most two black beads have white beads next to them?

• A. $\frac{2N}{2N+1}$
• B. $\frac{N^2}{(N-1)(N-1)!}$
• C. $\displaystyle{}\frac{N}{N-1} \sum_{k=1}^{N-1} \frac{1}{\left(\begin{array}{l}N \\ k\end{array}\right)}$
• D. $\displaystyle{}\frac{1}{N}+\sum_{k=1}^{N-1} \frac{1}{\left(\begin{array}{l}N \\ k\end{array}\right)}$
• E. None of the above

Answer 1

Probability of choosing a number k uniformly at random from {1,…,N−1} = $\frac{1}{N-1}$

Number of way to choose k beads from N white beads = $\binom{N}{k}$

Number of way in which k black beads can occur sequentially in the circle = N

Required Probability = $\frac{1}{N-1}*\frac{N}{\binom{N}{1}} + \frac{1}{N-1}*\frac{N}{\binom{N}{2}} + .... + \frac{1}{N-1}*\frac{N}{\binom{N}{N-1}}$

                                     = $\frac{N}{N-1}\sum_{k = 1}^{N - 1}\frac{1}{\binom{N}{k}}$

Answer  : C