7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ DC doesn't count? $\endgroup$ – Ari Brodsky Nov 17 '16 at 9:09
  • $\begingroup$ $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? $\endgroup$ – Henry Nov 17 '16 at 14:59
  • 1
    $\begingroup$ consider the worst case and add 1 $\endgroup$ – I am Back Nov 17 '16 at 15:01
13
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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$

$\endgroup$
4
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.