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

Starting with the result $\P(A\cup B) = \P(A)+P(B) - \P(A\cap B)$, prove that 
\[
\P(A\cup B\cup C) = \P(A)+\P(B)+\P(C)  
- \P(A\cap B) - \P(B\cap C) - \P(C \cap A)
+ \P(A\cap B\cap C)
\,.
\] 
Write down, without proof, the  corresponding result for four events $A$, $B$, $C$ and $D$.
A pack of $n$ cards, numbered $1, 2, \ldots, n$, is shuffled and laid out in a row. The result of the shuffle is that each card is equally likely to be in any position in the row. Let $E_i$ be the event that the card bearing the number $i$  is in the $i$th position in the row. Write down the following probabilities:
\begin{questionparts}
\item $\P(E_i)$;
\item $\P(E_i\cap E_j)$, where $i\ne j$;
\item  $\P(E_i\cap E_j\cap E_k)$, where $i\ne j$, $j\ne k$ and $k\ne i$.
\end{questionparts} 
Hence show that the probability that at least one card is in the same position as the number it bears is
\[
1 - \frac 1 {2!} + \frac 1{3!} - \cdots + (-1)^{n+1} \frac 1 {n!}\,.
\]
Find the probability that exactly one card is in the same position as the number it bears

Solution (Optional)

\begin{align*}
&& \mathbb{P}(A \cup B \cup C) &= \mathbb{P}(A \cup B) + \mathbb{P}(C) - \mathbb{P}((A \cup B) \cap C) \tag{applying with $A\cup B$ and $C$} \\
&&&=  \mathbb{P}(A \cup B) + \mathbb{P}(C) - \mathbb{P}((A \cap C) \cup (B \cap C)) \\
&&&=  \mathbb{P}(A)+\mathbb{P}(B) - \mathbb{P}(A\cap B) + \mathbb{P}(C) - \mathbb{P}((A \cap C) \cup (B \cap C))  \tag{applying with $A$ and $B$}\\
&&&=  \mathbb{P}(A)+\mathbb{P}(B) - \mathbb{P}(A\cap B) + \mathbb{P}(C) - \left ( \mathbb{P}(A \cap C) +\mathbb{P}(B \cap C) - \mathbb{P}( (A \cap C) \cap (B \cap C) )\right) \\
&&&= \mathbb{P}(A)+\mathbb{P}(B) +\mathbb{P}(C)- \mathbb{P}(A\cap B)- \mathbb{P}(A \cap C) -\mathbb{P}(B \cap C)+\mathbb{P}( A \cap B \cap C)
\end{align*}

\[ \mathbb{P}(A_1 \cup A_2 \cup A_3 \cup A_4) = \sum_i \mathbb{P}(A_i) -  \sum_{i \neq j} \mathbb{P}(A_i \cap A_j) + \sum_{i \neq j \neq j} \mathbb{P}(A_i \cap A_j \cap A_k) - \mathbb{P}(A_1 \cap A_2 \cap A_3 \cap A_4) \]

\begin{questionparts}
\item $\mathbb{P}(E_i) = \frac{1}{n}$
\item $\mathbb{P}(E_i \cap E_j) = \frac{1}{n} \cdot \frac{1}{n-1} = \frac{1}{n(n-1)}$ 
\item $\mathbb{P})(E_i \cap E_j \cap E_k) = \frac{1}{n(n-1)(n-2)}$
\end{questionparts}

First notice that the probability that $k$ (or more) cards are in the correct place is $\frac{(n-k)!}{n!}$ (place the other $n-k$ cards in any order. We are interested in:

\begin{align*}
\mathbb{P} \left ( \bigcup_{i=1}^n E_i \right) &= \sum_{i} \mathbb{P}(E_i) - \sum_{i \neq j} \mathbb{P}(E_i \cap E_j) +  \sum_{i \neq j \neq k} \mathbb{P}(E_i \cap E_j \cap E_k) - \cdots  \\
&= \sum_i \frac1n - \sum_{i\neq j} \frac{1}{n(n-1)} + \sum_{i \neq j \neq k} \frac{1}{n(n-1)(n-2)} -  \cdots  + (-1)^{k+1} \sum_{i_1 \neq i_2 \neq \cdots \neq i_k} \frac{(n-k)!}{n!} + \cdots\\
&= 1 - \binom{n}{2} \frac{1}{n(n-1)} + \binom{n}{3} \frac{1}{n(n-1)(n-2)} - \cdots + (-1)^{k+1} \binom{n}{k} \frac{(n-k)}{n!} + \cdots \\
&= 1 - \frac12 + \frac1{3!} - \cdots + (-1)^{k+1} \frac{n!}{k!(n-k)!} \frac{(n-k)!}{n!} + \cdots \\
&= 1 - \frac1{2!} + \frac1{3!} - \cdots + (-1)^{k+1} \frac{1}{k!} + \cdots + (-1)^{n+1} \frac{1}{n!} 
\end{align*}

The probability exactly one card is in the right place is the probability none of the other $n-1$ are in the right place, which is:

$\frac1n \left (1 - \left (1 - \frac1{2!} + \frac1{3!} - \cdots + (-1)^{k+1} \frac{1}{k!} + \cdots + (-1)^{n} \frac{1}{(n-1)!}  \right) \right)$

but there are also $n$ cards we can choose to be the card in the right place, hence

$\frac{1}{2!} - \frac{1}{3!} + \cdots +(-1)^n \frac{1}{(n-1)!}$

Preview

Problem

Solution

Cancel

Current Ratings

Difficulty Rating: 1600.0

Difficulty Comparisons: 0

Banger Rating: 1503.2

Banger Comparisons: 2