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.

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?

share|improve this question
add comment

4 Answers

up vote 11 down vote accepted

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

share|improve this answer
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. –  anonymous Apr 19 '12 at 12:19
add comment

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

share|improve this answer
    
This is what I thought initially, but you'll get 45 groups this way. The first coordinates would need to range from 1 to 45, with the second coordinate being 5 bigger than the first. Your method of counting leaves out, for example, (6, 11). –  Austin Mohr May 24 '11 at 5:41
    
@Austin: No, this answer is right. It gives 25 pairs (10k+r, 10k+r+5), for 0≤k≤4, 1≤r≤5. So of the 26 students some two must be in the same pair. Pairs like (6,11) are left out intentionally; they can be ignored. –  ShreevatsaR May 24 '11 at 13:58
    
@ Austin: I thought it is clear, we only use each number once. The first 5 pairs cover all numbers from 1 to 10. We already used 6,7,8,9,10, we don't use them again. Next five pairs would be $(11,16), (12,17), (13,18), (14, 19), (15, 20)$ and then we move to 21-30 range.... Shreev explained it much better, I tried to wrote it as elementary as possible.... –  N. S. May 24 '11 at 15:55
1  
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. :) –  Austin Mohr May 24 '11 at 19:04
add comment

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.

share|improve this answer
    
Yes, I've done that... but I'm not too sure how to apply it. –  meiryo May 23 '11 at 23:52
    
How many students live in houses in one group? And how many houses are in the group? –  Ross Millikan May 23 '11 at 23:52
add comment

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?

share|improve this answer
    
This is also a very good way of seeing it! –  meiryo May 24 '11 at 0:05
add comment

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.