Solution: 2018 Winter Midterm - 6

Author: Michiel Smid

Question

In the city of ShortLastName, every person has a last name consisting of one uppercase letter, followed by two lowercase letters. No two letters in a last name can be equal. Thus, Lin is a valid last name, whereas Xax is not a valid last name.
What is the minimum size of the population of ShortLastName, such that there must be at least two people who have the same last name?

(a)

$1 + 24 \cdot 25 \cdot 26$

(b)

$1 + 26!$

(c)

$1 + 26^{3}$

(d)

$1 + \frac{24 \cdot 25 \cdot 26}{3!}$

Solution

We can use pigeonhole principle to solve this problem.

We need to have 1 more than the maximum number of possible last names.

That way, we can guarantee that if all people have different last names, the last person will have a duplicate.

There are $ 26 $ possible uppercase letters for the first letter of the last name.

There are $ 25 $ possible lowercase letters for the second letter of the last name.

There are $ 24 $ possible lowercase letters for the third letter of the last name.

Thus, the minimum size of the population of ShortLastName is $ 26 \cdot 25 \cdot 24 + 1 $.