Solution: 2017 Winter Final - 15

Author: Michiel Smid

Question

Let $n \geq 5$ be an integer. Consider a uniformly random permutation $a_1a_2 \dots a_n$ of the set $\{1,2,\dots,n\}$. Define the events

What is $\Pr(A \cup B)$?

(a)

${\frac{1}{n}} - {\frac{1}{n(n-1)}}$

(b)

None of the above.

(c)

${\frac{2}{n}} - {\frac{1}{n^{2}}}$

(d)

${\frac{2}{n}} - {\frac{1}{n(n-1)}}$

Let's determine A
The probability that $a_1 = 1$ is $ \frac{1}{n} $
$ Pr(A) = \frac{1}{n} $
Let's determine B
The probability that $a_n = 5$ is $ \frac{1}{n} $
$ Pr(B) = \frac{1}{n} $
Let's determine $ A \cap B $
The probability that both $a_1 = 1$ and $a_n = 5$ is $ \frac{1}{n^2} $
$ Pr(A \cap B) = \frac{1}{n^2} $

$ Pr(A \cup B) = Pr(A) + Pr(B) - Pr(A \cap B) $

$ Pr(A \cup B) = \frac{1}{n} + \frac{1}{n} - \frac{1}{n} \frac{1}{n-1} $

$ Pr(A \cup B) = \frac{2}{n} - \frac{1}{n(n-1)} $