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.

I am choosing $m+1$ integers from the set $\lbrace 1,2,\ldots 2m\rbrace$, and I want to use the Pigeonhole Principle to show that two of the numbers chosen differ by $1$. I want to know if my strategy (below) is accepted so that I may turn to it in more complicated problems. If it is not, please state why. I am not looking for a solution to this problem (and I can solve it in a way that doesn't use the construction below), so please do not solve it.

My Solution: We have $m$ boxes, and we reserve the 1st box for 1 and 2, the 2nd box for 3 and 4, ..., and the mth box for $2m-1,2m$. Since we're distributing $m+1$ objects into $m$ boxes, by the Pigeonhole Principle, there is a box which has two elements. By construction, the difference of these two elements is 1.

Q: Am I allowed to place reservations on my boxes?

share|improve this question
3  
I’d turn it around and speak of choosing $m+1$ numbers from those same $m$ boxes and therefore having to choose two from the same box, but yes, that argument is fine. –  Brian M. Scott Feb 5 '13 at 5:09

1 Answer 1

The arguement to me looks ok, because if you select $m+1$ objects from $m$ boxes you must end up picking two from atleast one box.

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.