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$ 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$ May 27, 2017 at 11:06

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .