11
$\begingroup$

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?

4 Answers 4

12

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

  • 1
    +1. I found this method very helpful. Another way of coming at the same conclusion is to see how many numbers I can pick which are not adjacent. What is the maximum amount of numbers one can pick from these 5 sets that are not adjacent? There are 10 numbers in one set; to pick non-adjacent numbers from it, I have to pick the numbers alternately (for example, from the 1st set, pick 1 but not 6; pick 11 but not 16, and so on); thus I can pick at most 5 numbers from each set. Since there are 5 sets, I can pick at most 25 numbers. But I want 26 numbers. Thus, there will be adjacent numbers.2012-04-19
5

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.

  • 0
    How many students live in houses in one group? And how many houses are in the group?2011-05-23
5

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....

  • 2
    I see now. You're throwing away some possible configurations and STILL finding a pair of houses of the desired type. I now prefer your answer to mine. :)2011-05-24
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?

  • 0
    This is also a very good way of seeing it!2011-05-24