# pigeonhole principle clarification

Would the following statement be applicable to the pigeonhole principle? Or can I simply do $100 \times 50 = 5000$?

What is least amount of students in a school to guarantee that there are at least 100 students from the same state?

• DC doesn't count? – Ari Brodsky Nov 17 '16 at 9:09
• $5000$ is the answer to different questions: What is the smallest number of students in a school to make it possible that there are at least 100 students from every state? or What is the smallest number of students in a school to make it possible that there are no more than 100 students from every state? – Henry Nov 17 '16 at 14:59
• consider the worst case and add 1 – I am Back Nov 17 '16 at 15:01

Your answer is not quite correct. The most you can have WITHOUT having 100 students from the same state is $50\cdot99=4950$; so, the minimum to guarantee it is $4950+1=4951$.

Although I didn't say 'by the Pigeonhole principle', that's what has happened here.

The minimum number to guarantee that would be $99\cdot 50+1=4951$. If you had fewer, say $4950$, then there's the possibility that there are exactly $99$ students from each state. Any one additional student from any state is enough at this point.

You can have $99$ students from each state before you get $100$ students from at least one state.

So construct a pigeon hole for each state. Then add the maximum number under the desired number to each one. So we get $99 \times 50 = 4950$ students. Then, the next one we add will push any single pigeon hole to $100$ pigeons students. So the minimum number of students for there to be 100 from at least one state is $(99 \times 50) + 1 = 4951$

Yes, assuming all the students will come from US, the college needs to have $99 (\text{number of states})+1$

• "from the US, and not from DC, PR, VI, GU, AS, or be expats without a 'permanent' address in any of the states" – Monty Harder Nov 17 '16 at 16:51