# Pigeonhole Principle

• Jul 20th 2007, 05:41 PM
Discrete
Pigeonhole Principle
Let d be a positive integer. Show that among any group of d +1 (not necessary consecutive) integers, there are two with exactly the same remainder when divided by d.
• Jul 20th 2007, 05:57 PM
Jhevon
Quote:

Originally Posted by Discrete
Let d be a positive integer. Show that among any group of d +1 (not necessary consecutive) integers, there are two with the same remainder when divided by 4.

i believe there is something missing from the question, or you're not describing something correctly. one thing i can see (i may be wrong) we have to have that \$\displaystyle d \geq 4\$, otherwise, we cannot show what we are being asked.

for the sake of illustration, let's say d = 1, that is a positive integer. so d + 1 would be 2. there is no guarantee, by the pigeonhole principle or otherwise, that any arbitrary group of two integers would have two elements that are congruent mod 4
• Jul 20th 2007, 06:20 PM
galactus

"Let d be a positive integer. Show that among any group of d+1 (not necessary consecutive) integers, there are two with the same remainder when divided by d".
• Jul 21st 2007, 05:32 PM
ThePerfectHacker
Given \$\displaystyle n+1\$ integers which are the "pigeons". Let the sets \$\displaystyle \{0\} , \{1\}, ... ,\{n-1\}\$ be the remainders upon division by \$\displaystyle n\$. Since there are \$\displaystyle n\$ holes and \$\displaystyle n+1\$ pigeons we conclude that two have the same remainder.
• Jul 22nd 2007, 07:01 AM
Discrete
Sorry guys I revised the question, there are some typo's there it should be divided by d
• Jul 22nd 2007, 07:21 AM
Jhevon
Quote:

Originally Posted by Discrete
Sorry guys I revised the question, there are some typo's there it should be divided by d

Yes, TPH's solution is valid for the revised question. he (and galactus) read through the lines and figured that's what you were really asking
• Jul 22nd 2007, 07:47 AM
Discrete
Quote:

Originally Posted by Jhevon
Yes, TPH's solution is valid for the revised question. he (and galactus) read through the lines and figured that's what you were really asking

I still don't get what TPH is saying, is the set {0}, {1}, ... {n-1} the remainder? if yes then where is the same remainder?
• Jul 22nd 2007, 08:00 AM
Jhevon
Quote:

Originally Posted by Discrete
I still don't get what TPH is saying, is the set {0}, {1}, ... {n-1} the remainder? if yes then where is the same remainder?

when you divide an integer by some other integer, the remainder can range from zero right up to 1 less than the number you divided by: if you divide by 4, the possible remainders are 0, 1, 2 and 3. If you divide by 2, the possible remainders are 0 and 1, if you divide by 5, the possible remainders are 0,1,2,3, and 4. if you go any greater than this, you repeat this cycle. let's say you could have more remainders than this. let's say if you divide by 2, your possible remainders could be 0,1, and 2. 0 and 1 are fine, but if the remainder is 2, you could simply get another factor of 2 out of the original number and have a remainder of zero.

TPH used that principle. We have n + 1 integers being divided by n, so the possible remainders are 0, 1, 2, 3, ..., (n - 1), one less than the number we divided by. if you count starting from 0 up to (n - 1) you get n remainders. look at my illustrations above, you will find if you divide by 2 you have 2 possible remainders, if you divide by 5, you have 5 possible remainders. so here, we have n possible remainders. but there are (n + 1) integers, meaning when you get to the nth integer, you would have exhausted the n remainders, so the next (n + 1)th integer must reuse one of the remainders already used, so there will be two numbers with the same remainder when divided by n

see here for more on the Pigeonhole Principle
• Jul 22nd 2007, 08:07 AM
Discrete
gotcha jhevon's, I got it a bit more clear now.. so the remainder here can be represented as the pigeons right? and n+1 is the hole/cage of the pigeon?
• Jul 22nd 2007, 08:11 AM
Jhevon
Quote:

Originally Posted by Discrete
gotcha jhevon's, I got it a bit more clear now.. so the remainder here can be represented as the pigeons right? and n+1 is the hole/cage of the pigeon?

no, the remainders are the holes, and the integers are the pigeons

if you pick an integer and it has a remainder of 0 when divided by n, then you put it in the hole for 0, if it has a remainder of 1 when divided by n, you put it in the hole for 1, and so on. eventually, after n consecutive integers, you would have filled all the holes, and the last integer must be put into a hole that is already used. (if the integers are not necessarily consecutive, and it is the case that you haven't filled the holes by the nth integer, it simply means you already reused one of the holes at least once, so there are already at least two integers with exactly the same remainder)