Remainders, Pigeons, and Pigeonholes
Date: 03/26/2003 at 18:05:29 From: Stephanie Subject: Pigeonhole Principle Seventeen integers are given. Prove that it is always possible to select five of the seventeen whose sum will be divisible by 5. I'm just not sure how to use PHP with this problem. When you divide by 5, there are 5 possible remainders: 0,1,2,3,4. Then these are the pigeonholes. But I'm confused; are the 17 integers the pigeons or are they the 5 you choose?
Date: 03/27/2003 at 10:18:46 From: Doctor Nbrooke Subject: Re: Pigeonhole Principle Hi Stephanie, and thanks for writing to Dr. Math. By the division algorithm, every integer has a unique remainder when divided by 5. As you said, the possible remainders are 0, 1, 2, 3, and 4: these are your pigeonholes. The 17 integers are your pigeons. Notice that if any remainder appears five or more times in your list of seventeen integers, then you can choose those 5 integers and take their sum, and it will be divisible by five. Observe: Let A, B, C, D, and E be integers all divisible by r, where r is between 0 and 4, inclusive. By the division algorithm, let A = 5a + r, B = 5b + r, and so on. Then A + B + C+ D + E = (5a + r) + (5b + r) + (5c + r) + (5d + r) + (5e + r). Since addition is commutative, we regroup to get (5a + 5b + 5c + 5d + 5e) + (r + r + r + r + r) = 5 (a + b + c + d + e) + 5r = 5((a + b + c + d + e) + r), which is divisible by 5. So now we know that if we have more than five in a pigeonhole, then your sum is divisible by 5. What other situation can you find where we know that we can find a sum divisible by 5, but there are still fewer than five pigeons in each hole? Figure this out, and the proof should practically finish itself for you. I hope this helps. If you have any more questions, please feel free to write back. - Doctor Nbrooke, The Math Forum http://mathforum.org/dr.math/
Date: 03/23/2003 at 07:24:44 From: Doctor Jacques Subject: Re: The pigeonhole principle Hi Jillian, We have indeed 17 pigeons and 5 holes. In this case, the holes are residue classes modulo 5. We want to show that we can find 5 numbers whose sum is congruent to 0 modulo 5. However, we must extend the pigeonhole principle to use the fact that we have "many" more pigeons than holes in this case. Assume first that one residue class (say k) contains at least 5 numbers. We can then select 5 numbers from that class, and the sum will be: 5k = 0 (mod 5) and we are done. We can now assume that no hole contains more than 4 pigeons. In such a case, no hole can be empty - can you show it? Now, we can pick one number from each residue class modulo 5 (as no such class is empty). The sum of these numbers is: 0 + 1 + 2 + 3 + 4 = (5*4)/2 = 0 mod 5 In general, if p is odd, and we have a set of N > (p-1)^2 numbers, we can always select p of them whose sum is a multiple of p. The argument is exactly the same. This problem raises some interesting questions: * Is it true for any even p (it is false for p = 2) ? * Is this the best possible bound ? For example, with p = 5, would it still be true for N = 16 ? Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum