Thread: Pigeon Hole problem!

how do i show that in any set of 6 integers, there must be at least two whose difference is divisible by 5?

thanks.

Kyle

Originally Posted by CSkyle

how do i show that in any set of 6 integers, there must be at least two whose difference is divisible by 5?
thanks.
Kyle

Pigeon Hole Principle
Observe that if two numbers leave the same remainder with 5, then their difference is divisible by 5. Since there are only 5 distinct remainders possible(i.e{0,1,2,3,4}), in a set of six numbers, at least 2 numbers must leave the same remainder when divided by 5(pigeon hole principle). So the conclusion follows.

Originally Posted by Isomorphism

Pigeon Hole Principle
Observe that if two numbers leave the same remainder with 5, then their difference is divisible by 5. Since there are only 5 distinct remainders possible(i.e{0,1,2,3,4}), in a set of six numbers, at least 2 numbers must leave the same remainder when divided by 5(pigeon hole principle). So the conclusion follows.

Nice solution.

So now you're kenshin! ...i don't want to battle kenshin.

Glad to see you are a part of TeamJ!

...they have cookies with new flavors now?!

why wasn't i told?! It's not like i'm the one always finishing the cookies, you know!