Solution: 2017 Winter Midterm - 8

Author: Michiel Smid

Question

Each student has a student number which is a string of five digits, in which no digit occurs more than once. Thus, 94631 is a valid student number, whereas 94641 is not valid.
What is the minimum number of students such that we can guarantee that at least two of them have the same student number?

(a)

$1 + \frac{5!}{10!}$

(b)

$1 + 5^{10}$

(c)

$1 + \frac{10!}{5!}$

(d)

$1 + 10^{5}$

Solution

We can use the pigeonhole principle. To guarantee that at least two of them have the same student number, we need to have one more student than the number of possible student numbers.

There are $ 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 $ possible student numbers.

We can rewrite this as…

$ \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6} \cdot 1 $

$ = \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} $

$ = \frac{10!}{5!} $

With the pigeonhole principle, we need to have $ \frac{10!}{5!} + 1 $ students to guarantee that at least two of them have the same student number.