Can the remainder of difference be used as pigeon-holes?

80 Views Asked by At

Given a problem as follows.

Prove that among 8 integers, there are always two whose difference is divisible by 7.

Method 1

The set of all possible remainders when dividing integers by 7 is $\{0,1,2,3,4,5,6\}$. Because there are 8 integers (pigeons) and 7 possible remainders (pigeon-holes), then at least two integers have the same remainder when divided by 7. The difference of this particular pair has zero remainder when divided by 7.

Method 2

The difference of two integers is an integer. Any integer has one of 7 possible remainders (pigeon-holes) when divided by 7. There are ${8\choose 2}=28$ ways to make differencing pairs (pigeons).

How to make sure there is at least one pair (among 28 possible pairs) with zero difference?

1

There are 1 best solutions below

0
On BEST ANSWER

This Method 2 doesn't really get us anywhere.

At least $4$ of the $28$ difference values have the same remainder mod $7$. So $(a-b)-(c-d)$ is a multiple of $7$. But then what?

This argument doesn't rule out the case where the paired differences have remainders $1$ through $6$, some remainders used at least $5$ times, but remainder zero used $0$ times.

The Pigeonhole Principle can be used to show some group of "pigeons" have a common unknown "hole" value, like Method 1 shows there are elements with the same unknown remainder. It can't be used to show that any pigeons at all are in a specific hole, like Method 2 is trying to see if any differences are in the specific "remainder zero" hole.