Solution: 2015 Fall Midterm - 7

Author: Michiel Smid

Question

In the city of $\ShortLastName$, every person has a last name consisting of two characters, the first one being an uppercase letter and the second one being a lowercase letter. What is the minimum number of people needed so that we can guarantee that at least 4 of them have the same last name?

(a)

$3 \cdot 26^{2} + 1$

(b)

$4 \cdot 26^{2}$

(c)

$4 \cdot 26^{2} + 1$

(d)

$3 \cdot 26^{2}$

Solution

We can use the pigeon hole principle.

There are $26 \cdot 26 = 26^2$ possible last names.

To guarantee that at least 2 people have the same last name, we need $26^2+1$ people.

To guarantee that at least 4 people have the same last name, we need $3 \cdot 26^2+1$ people.