Question

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?)

Answer 1

Step-by-step 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).