Edit Problem

Year

Paper

Question Number

Course

Section

Worksheet Citation (for copying)

Click the copy button or select the text to copy this citation for use in worksheets.

Problem Text

Each day, I have to take $k$ different types of medicine, one tablet of each. The tablets are identical in appearance. When I go on holiday for $n$ days, I put $n$ tablets of each type in a container and on each day of the holiday I select $k$ tablets at random from the container.
\begin{questionparts}
\item In the case $k=3$, show that the probability that I will select one tablet of each type on the first day of a three-day holiday is $\frac9{28}$. Write down the probability that I will be left with one tablet of each type on the last day (irrespective of the tablets I select on the first day).
\item In the case $k=3$, find the probability that I will select one tablet of each type on the first day of an $n$-day holiday. 
\item In the case $k=2$,   find the probability that I will select one tablet of each type on each day of an $n$-day holiday, and use Stirling's approximation 
\[
n!\approx \sqrt{2n\pi} \left(\frac n\e\right)^n
\]
to show that this probability is approximately $2^{-n} \sqrt{n\pi\;}$.
\end{questionparts}

Solution (Optional)

\begin{questionparts}
\item The probability the first is different to the second is $\frac68$, the probability the third is different to both of the first two is $\frac37$ therefore the probability is $\frac{6}{8} \cdot \frac37 = \frac9{28}$

Whatever pills we are left with on the last day is essentially the same random choice as we make on the first day, therefore $\frac9{28}$

\item The probability the first is different to the second is $\frac{2n}{3n-1}$, the probability the third is different to both of the first two is $\frac{n}{3n-2}$ therefore the probability is $\frac{2n^2}{(3n-1)(3n-2)}$.

[We can also view this as $\frac{(3n) \cdot (2n) \cdot n}{(3n) \cdot (3n-1) \cdot (3n-2)}$]

\item Suppose describe the pills as $B$ and $R$ and also number them, then we must have a sequence of the form:

\[ B_1R_1 \, B_2R_2 \, B_3R_3 \, \cdots \, B_{n}R_n \]

However, we can also rearrange the order of the $B$ and $R$ pills in $n!$ ways each, and also the order of the pairs in $2^n$ ways. There are $(2n)!$  orders we could have taken the pills out therefore the probability is

\begin{align*}
&& P &= \frac{2^n (n!)^2}{(2n)!} = \frac{2^n}{\binom{2n}{n}} \\
&&&\approx \frac{2^n \cdot 2n \pi \left ( \frac{n}{e} \right)^{2n}}{\sqrt{2 \cdot 2n \cdot \pi} \left ( \frac{2n}{e} \right)^{2n}} \\
&&&= \frac{2^n \sqrt{n \pi} \cdot n^{2n} \cdot e^{-2n}}{2^{2n} \cdot n^{2n} \cdot  e^{-2n}} \\
&&&= 2^{-n} \sqrt{n \pi}
\end{align*}

There is a nice way to think about this question using conditional probability. Suppose we are drawing out of an infinitely supply of $R$ and $B$ pills, then each day there is a $\frac12$ chance of getting different pills. Therefore over $n$ days there is a $2^{-n}$ chance of getting different pills. Conditional on the balanced total we see that

\begin{align*}
&& \mathbb{P}(\text{balanced every day} |\text{balanced total}) &= \frac{\mathbb{P}(\text{balanced every day})}{\mathbb{P}(\text{balanced total})} 
\end{align*}

We have already seen the term that is balanced total is $\frac{1}{2^{2n}}\binom{2n}{n}$, but we can also approximate the balanced total using a normal approximation. $B(2n, \tfrac12) \approx N(n, \frac{n}{2})$ and so:

\begin{align*}
\mathbb{P}(X = n) &\approx \mathbb{P}\left (n-0.5 \leq \sqrt{\tfrac{n}{2}} Z + n \leq  n+0.5 \right) \\
&= \mathbb{P}\left (- \frac1{\sqrt{2n}} \leq Z \leq \frac{1}{\sqrt{2n}} \right) \\
&= \int_{- \frac1{\sqrt{2n}}}^{\frac1{\sqrt{2n}}} \frac{1}{\sqrt{2\pi}} e^{-x^2/2} \d x \approx \frac{2}{\sqrt{2n}} \frac{1}{\sqrt{2\pi}} \\
&\approx \frac{1}{\sqrt{n\pi}}

\end{align*}

\end{questionparts}

Preview

Problem

Solution

Cancel

Current Ratings

Difficulty Rating: 1500.0

Difficulty Comparisons: 0

Banger Rating: 1468.0

Banger Comparisons: 2