13
$\begingroup$

Let $x_1,x_2,x_3,x_4,x_5,x_6$ be given integers, not divisible by $7$. Prove that at least one of the expressions of the form $$\pm x_1\pm x_2\pm x_3\pm x_4\pm x_5\pm x_6$$ is divisible by $7$, where the signs are selected in all possible ways. (Generalize the statement to every prime number greater than two!)

Each term is in $\{1,2,3,4,5,6\}$ modulo $7$, but how do I use this to prove the result?

$\endgroup$
8
  • $\begingroup$ Are you assuming that the $x_i$ span the non-zero residues? If so, see this question $\endgroup$
    – lulu
    Jun 7, 2016 at 14:16
  • $\begingroup$ Of course, for that case you could just pair each element with its additive inverse...so I suppose the problem is only interesting if the $x_i$ don't span the residues. $\endgroup$
    – lulu
    Jun 7, 2016 at 14:31
  • 3
    $\begingroup$ use $\{-3,-2,-1,1,2,3\}$ as your set of residues instead of 1-6. Also, note that the same sums can be obtained from $|x_1|,...,|x_6|$ as can be obtained from $x_1, ..., x_6$, so you only need to consider terms in $\{1,2,3\}$. $\endgroup$
    – Paul Sinclair
    Jun 7, 2016 at 16:56
  • 4
    $\begingroup$ Follows very easily from Cauchy-Davenport: mathworld.wolfram.com/Cauchy-DavenportTheorem.html $\endgroup$
    – Erick Wong
    Jun 8, 2016 at 0:45
  • 1
    $\begingroup$ @ErickWong: Maybe consider making your comment an answer, so that it can be accepted and this question can exit the queue? $\endgroup$
    – Kieren MacMillan
    May 27, 2017 at 11:06

1 Answer 1

Reset to default
2
$\begingroup$

I didn't see a direct pigeonhole argument, but it is very easy to prove this using Cauchy-Davenport (which itself is fairly elementary).

We make the simple observation that an alternating sum $\pm x_1 \pm \cdots \pm x_6$ is $0$ iff twice the sum of the positive terms is equal to $x_1 + \cdots + x_6$. This principle also works modulo $7$, so the claim holds if we know that some subset of $\{x_1,\ldots,x_6\}$ sums to a number congruent to $2^{-1}(x_1+\cdots+x_6)$ mod $7$. Cauchy-Davenport assures us that in fact every possible residue is covered.

This generalizes completely to any prime except for $2$ (since we use the fact that $2$ has a multiplicative inverse). For $p=2$ we only have one term (and the $\pm$ signs have no effect) so it the analogous claim is false.

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