0
$\begingroup$

Imagine, in the school there are 25,000 students, at least one from each of 50 states. Than must be a group of 500 students coming from same state.

I don't know what to count the 25,000 students or 500 students.

Question How can I prove the pigenhole principle in this case?

Attempt I know, If $k$ is a positive integer and $k+1$ or more objects are placed into $k$ boxes , than there is at least one box containing two or more of the objects. I don't know what to count the 25,000 students or 500 students ?

$\endgroup$
  • 1
    $\begingroup$ What are you asking? $\endgroup$ – Zain Patel Jul 3 '15 at 3:52
  • 1
    $\begingroup$ I know, If k is a positive integer and k+1 or more objects are placed into k boxes , than there is at least one box containing two or more of the objects. $\endgroup$ – Betty Jul 3 '15 at 4:05
  • 1
    $\begingroup$ I don't know what to count the 25,000 students or 500 students ? $\endgroup$ – Betty Jul 3 '15 at 4:07
  • 1
    $\begingroup$ Students are objects. Each state has $499$ boxes. $\endgroup$ – Robert Israel Jul 3 '15 at 4:09
  • 1
    $\begingroup$ If each state had fewer than $500$ students, you'd be able to fit all its students into the boxes, one student per box. But there are only ... boxes in all ... $\endgroup$ – Robert Israel Jul 3 '15 at 4:13
3
$\begingroup$

Based on your understanding of the pigeonhole principle, you know that if there are 51 students, then there is at least one state with at least 2 students.

Similarly, if there are 101 students, then there is at least one state with at least 3 students.

If there were $50n+1$ students, then there is at least one state with at least $n+1$ students.

Can you do the rest?

$\endgroup$
  • $\begingroup$ I'm waiting for the answer. It is not clear to me. $\endgroup$ – Betty Jul 3 '15 at 4:18
  • $\begingroup$ Not yet. Can you write a little more? $\endgroup$ – Betty Jul 3 '15 at 4:26
  • 1
    $\begingroup$ If there were 24950 students, then it would be possible that no state has 500 students (this would be the case if each state has 499 students). But if there were 24951 students ... $\endgroup$ – Joel Reyes Noche Jul 3 '15 at 4:28
  • $\begingroup$ What is n? 500 students? $\endgroup$ – Betty Jul 3 '15 at 4:29
  • 1
    $\begingroup$ Thank you for your help, I understand now. $\endgroup$ – Betty Jul 3 '15 at 4:39
2
$\begingroup$

Suppose the contrary: there are at most $499$ students from each state. Then, there are at most $499\times50$ students in total, which contradicts the fact that there are $25000$ students.

$\endgroup$
  • $\begingroup$ That sound good to me, thank you. $\endgroup$ – Betty Jul 3 '15 at 4:21
  • $\begingroup$ But you suppose to add 1 not subtract number 1. $\endgroup$ – Betty Jul 3 '15 at 4:23
  • $\begingroup$ @Betty What do you mean by "add 1 not subtract number 1"? $\endgroup$ – Eclipse Sun Jul 3 '15 at 4:29

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.