Pigeonhole Principle Issue five integers where their sum or difference is divisible by seven.

Question

Given any five integers, there will be two that have a sum or difference divisible by 7. I'm trying to solve this using the Pigeonhole Principle, but it is not making sense to me, how this principle holds true in this case. Aren't the "pigeons" in this case "five" and the "holes" are "seven"? I'm so confused.

Answer 1

consider $a_n = x_n \mod 7$ In order to avoid a difference divisible by 7, all 5 $a_n$ must be distinct.

In order to avoid a sum divisible by 7, no two $a_n$ can sum to 7

So we actually have only 4 holes in which to put our 5 $a_n$

1) $a_n=0$

2) $a_n = 1 $ or $a_n = 6$

3) $a_n = 2 $ or $a_n = 5$

4) $a_n = 3 $ or $a_n = 4$

To avoid a sum or difference divisible by 7 we would need to put 5 integers into 4 holes with no more than one in each hole. This can't be done, therefore having at least one pair whose sum or difference is divisible by 7 is unavoidable.

Answer 2

Here is another argument which is based on the following fact:

• There are only $4$ quadratic remainders $\mod 7$: $0,1,2,4$.

Now, let $a_1, \ldots , a_5 \in \mathbb{Z}$.

• There is $1\leq k < l \leq 5$ such that

$$a_k^2 \equiv a_l^2 \mod 7 \Rightarrow (a_k + a_l)(a_k - a_l) \equiv 0 \mod 7$$ This proves the claim.

Answer 3

Note every integer $a$ is such that $a \equiv 0, \pm 1, \pm 2, \pm 3 \pmod 7$.

Let the pigeons be the $5$ integers. Let $k = 0, 1, 2, 3$ be the $4$ holes.

We assign pigeons to holes:

We assign pigeon $a$ the hole $k$ if $a \equiv \pm k \pmod 7$.

Two pigeons must share the same hole:

There are five pigeons so we are going to have two pigeons, $a$ and $b$ in the same hole, $k$. i.e. $a \equiv \pm k \pmod 7$ and $b \equiv \pm k \pmod 7$.

which means:

So $a \equiv \pm b \pmod 7$. So $a \mp b \equiv 0 \pmod 7$. So either $a + b$ is divisible by $7$ or $a-b$ is divisible by $7$.

.