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$
3
  • $\begingroup$ DC doesn't count? $\endgroup$ Commented Nov 17, 2016 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
    Commented Nov 17, 2016 at 14:59
  • 1
    $\begingroup$ consider the worst case and add 1 $\endgroup$ Commented Nov 17, 2016 at 15:01

4 Answers 4

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$
1
  • 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$ Commented Nov 17, 2016 at 16:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .