113k views
1 vote
Suppose you pick 6 different numbers in [10]. Prove that 2 of the numbers are next to each other. (Hint: use the pigeonhole principle. What are the pigeons and what are the holes?)

User Prule
by
5.5k points

1 Answer

1 vote

Explanation:

We are picking 6 numbers from the numbers 1,2,3,4,5,6,7,8,9,10. Since we care about numbers being next to each other, we might think of the 10 numbers as being distributed in 5 boxes (which you can think of as the holes):

| 1 2 | 3 4 | 5 6 | 7 8 | 9 10 |

So on the first box we have the numbers 1 and 2, on the second box we have the numbers 3 and 4, and so on. Since we are picking 6 numbers from those 10 numbers, that means we'll have to pick 6 boxes (and inside each box we pick a number), but we only have 5 available boxes, so by the pigeonhole principle, we'll have to pick 1 same box at least two times. Since on each picked box we'll need to pick a number, on this box which was picked two times, we will have to pick both of its numbers. And so those 2 numbers inside that box will be next to each other (meaning they're consecutive numbers).

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.