Prove that 2 students live exactly five houses apart if

Question

There are 50 houses along one side of a street. A survey shows that 26 of these houses have students living in them. Prove that there are two students who live EXACTLY five houses apart on the street.

How do I use the pigeonhole principle for this question?

Answer 1

Number the houses sequentially from 1 to 50. Define 5 pigeonholes using the house numbers (1, 6, 11, ..., 46), (2, 7, 12, ..., 47), ..., (5, 10, 15, ..., 50).

Since you are distributing 26 pigeons into these 5 pigeonholes, one of them receives at least 6 pigeons. Since there are 6 pigeons (i.e. 6 numbers are being chosen), it must be that two of them are adjacent. (You can make this last statement more precise with ANOTHER pigeonhole argument.)

Answer 2

Hint: divide the houses into groups $(1,6,11,\ldots,46), (2,7,12,\ldots,47),$ etc.

Added after the fact: Even easier: consider the pairs $(k,k+5)$ for $1 \le k \pmod {10} \le 5$. There are 25 of them. Only one application of the principle.

Answer 3

You can use the possible remainders after division as your holes. If we number the houses from $1$ to $50$, we can see that $10$ of them have a remainder of $0$ after dividing by $5$, $10$ have a remainder of $1$, and so on. Within each group of ten, I can pick five houses such that none of them are five units apart. This allows me to place $25$ houses ($5$ houses for each of $5$ remainders). Where does the $26^{\text{th}}$ house go?

Answer 4

You can also divide the houses in 25 groups of 2 houses:

$(1,6), (2,7), (3,8), (4,9), (5,10)$ and add 10, 20 , 30, 40 for the other $4*5=20$ groups.

26 students, 25 pairs....