Solution: 2016 Fall Final - 17

Author: Michiel Smid

Question

Let $X = \{1,2,\dots,100\}$. We choose a uniformly random subset $Y$ of $X$ having size 17. Define the event

A = "$4 \in Y$ or $7 \in Y$".

What is $\Pr(A)$?

(a)

$\frac{2 \cdot {99 \choose 16}}{100 \choose 17}$

(b)

$1 - \frac{{100 \choose 2} \cdot {98 \choose 15}}{100 \choose 17}$

(c)

$1 - \frac{{98}\choose{15}}{{100}\choose{17}}$

(d)

$\frac{2 \cdot {99 \choose 16} - {98 \choose 15}}{100 \choose 17}$

Solution

Let's determine $ S $
S is the set of all possible outcomes of the 17 students
$ |S| = \binom{100}{17} $
Let's determine $ B $
B occurs when 4 is in the subset
We choose 4: 1
We choose 16 from the remaining 99: $ \binom{99}{16} $
$ |B| = 1 \cdot \binom{99}{16} $
$ Pr(B) = \frac{1 \cdot \binom{99}{16}}{\binom{100}{17}} $
Let's determine $ C $
C occurs when 7 is in the subset
We choose 17: 1
We choose 16 from the remaining 99: $ \binom{99}{16} $
$ |C| = 1 \cdot \binom{99}{16} $
$ Pr(C) = \frac{1 \cdot \binom{99}{16}}{\binom{100}{17}} $
Let's determine $ B \cap C $
We choose 17: 1
We choose 4: 1
We choose 15 from the remaining 98: $ \binom{98}{15} $
$ |B \cap C| = 1 \cdot 1 \cdot \binom{98}{15} $
$ Pr(B \cap C) = \frac{1 \cdot 1 \cdot \binom{98}{15}}{\binom{100}{17}} $

Now, let’s determine $ A $

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

$ Pr(A) = \frac{1 \cdot \binom{99}{16}}{\binom{100}{17}} + \frac{1 \cdot \binom{99}{16}}{\binom{100}{17}} - \frac{1 \cdot 1 \cdot \binom{98}{15}}{\binom{100}{17}} $

$ Pr(A) = \frac{2 \cdot \binom{99}{16} - \binom{98}{15}}{\binom{100}{17}} $