Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove the following version of the pigeonhole principle. Let $m$ and $n$ be positive integers. If $m$ objects are distributed in some way among $n$ containers, then at least one container must hold at least $1 + \left\lfloor\frac {m − 1}{n}\right\rfloor$ objects.

share|improve this question
1  
Setting $m=4; n=2$ we have that one of the two containers must hold $1+\frac{4-1}2=1+\frac32=2\frac12$ objects. But what is $\frac12$ an object? And why can't I just put two objects in each container? Last I checked, two pints of beer were less than two pints and half a pint of beer. –  Asaf Karagila Dec 3 '12 at 20:47
1  
Did you perhaps mean $$\left\lfloor 1+\frac{m-1}{n}\right\rfloor$$ instead? (That may also be false, but it avoids the problem that Asaf pointed out.) –  Cameron Buie Dec 3 '12 at 20:49
1  
Cameron's version is correct, and the original post (before editing) did in fact have brackets indicating the floor function. Unfortunately someone saw fit to delete them. –  Jonathan Christensen Dec 3 '12 at 21:01
    
As for the proof, it's easy to do by contradiction. Have you tried that? –  Jonathan Christensen Dec 3 '12 at 21:02
1  
I believe you can do it by using a generalized PP, If more than mn+1 objects are distributed among n boxes, then at least one box has at least m+1 objects. –  dani Dec 4 '12 at 16:46

1 Answer 1

HINT: Suppose that each container holds at most $\left\lfloor\dfrac{m-1}n\right\rfloor$ objects. Then it’s certainly true that each container holds at most $\dfrac{m-1}n$ objects. (Why?) What does that tell you about the maximum possible total number of objects in all $n$ containers?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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