3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Hint: How many sums are possible? How many differences are possible? $\endgroup$ – JoshuaZ Oct 24 '18 at 2:40
  • 1
    $\begingroup$ The 7 holes are not $0,1,2,3,4,5,6,7$. The 4 holes are $0, \pm 1, \pm 2, \pm 3$ $\endgroup$ – fleablood Oct 24 '18 at 6:39
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why argue by contradiction? If two integers have equal quadratic remainder, then either their sum or their difference is a multiple of 7, and you are done. $\endgroup$ – Andrés E. Caicedo Oct 24 '18 at 4:36
  • $\begingroup$ @ Andrés E. Caicedo: Ha!. That's right. It's still early here in the morning. Will edit it accordingly. :-) Thanks. $\endgroup$ – trancelocation Oct 24 '18 at 4:44
4
$\begingroup$

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$.

.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.