Minimum number of students, where 100 students from the same state go to the same university

Question

I was given the following question:

I thought of the problem like this. Each of the $50$ states represents a box, and I want $100$ people in the same box. By the pigeon-hole principle, we are trying to find $N/50 \geq 100 \Longrightarrow N = 50*100 = 5000$. It turns out I was close, my textbook gave the answer $4,951$ and I'm wondering why I was wrong?

Answer 1

What version of the pigeonhole principle are you using? There are various ways of doing it with floor and/or ceiling functions, but IMHO the simplest version is the one involving strict inequalities.

If more than $nk$ objects are placed into $n$ boxes, there must be a box containing more than $k$ objects.

In your problem you want to end up with at least $100$ objects in the same box, that is, more than $99$, so $k=99$. Clearly you have $n=50$ boxes. To guarantee what you want, you need more than $50\times99$ objects altogether, so the smallest possibility is $50\times99+1$.

Answer 2

Hint: $4951 = 99\times 50 + 1$.

---

If you have 4950 students, it may be the case that there are 99 per state. If you have one more, there must be at least one state with 100 students (the "worst" that can happen is that all but one state have 99 students, and the last one has 100).