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?
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.
|
asked |
|
|
viewed |
241 times |
|
active |
