14
$\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$
  • $\begingroup$ Are you assuming that the $x_i$ span the non-zero residues? If so, see this question $\endgroup$ – lulu Jun 7 '16 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 '16 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 '16 at 16:56
  • 4
    $\begingroup$ Follows very easily from Cauchy-Davenport: mathworld.wolfram.com/Cauchy-DavenportTheorem.html $\endgroup$ – Erick Wong Jun 8 '16 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 '17 at 11:06
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.