# A Pigeonhole-Principle from IMO Shortlist.

I have solved a great many pigeonhole principle problems so far. Now I am stuck with this.The statement of the problem runs as follows-

Let $$p$$ be an odd prime. Consider $$p-1$$ positive integers $$x_1,x_2,x_3,...,x_{p-1}$$, none of which is divisible by $$p$$. Then consider all possible sums of the form $$\pm x_1 \pm x_2 \pm x_3 \pm \cdots \pm x_{p-1}$$. Clearly there are $$2^{p-1}$$ such sums. Prove that at least one among these sums is divisible by $$p$$.

• Can we use Euler's theorem here?
– ShBh
Nov 6, 2017 at 8:27
• Euler's theorem seems like a strange thing to look for, since there are no exponents to speak of. I mean, it's an IMO shortlist, so it's possible that the solution in some convoluted way involves Euler's, but it wouldn't be my first choice of approach. Nov 6, 2017 at 8:29
• @Arthur Actually I thought about the congruence $2^{P-1}≡1 (mod P)$ for $P$ prime
– ShBh
Nov 6, 2017 at 8:50
• $2^{p-1}$ is just counting the number of different sums (i.e. the number of pigeons). Manipulating that with Euler's makes no sense, at least to me. It is the sums themselves (i.e. the actual pigeons) that you have to manipulate with modular arithmetic, not the number of sums. Nov 6, 2017 at 8:58
• @ShubhrajitBhattachrya Yeah, I forgot to mention that. Nov 6, 2017 at 9:10

We will prove by induction the following

Claim. Let $1\le k \le p-1$ be an integer. Suppose that $x_1, x_2, \ldots, x_k$ are integers, none of them divisible by $p$. Then the set $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \}$$ has at least $k+1$ elements.

Proof. If $k=1$ then the thesis is true. Indeed, since $p \nmid x_1$, $$x_1 \not\equiv -x_1 \pmod p \iff 1 \not\equiv -1 \pmod p$$ which is true as $p$ is odd.

Suppose now that for some $1\le k<p-1$ the set $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \}$$ has at least $k+1$ elements. If this set has $k+2$ distinct elements then clearly the set $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k + x_{k+1} \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \}$$ has at least $k+2$ elements and therefore its superset $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k + \varepsilon_{k+1} x_{k+1} \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k,k+1 \}$$ has at least $k+2$ elements as well. Thus the thesis of the claim is true in this case.

Suppose now that the set $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \}$$ has exactly $k+1$ elements. Let $y_1, y_2, \ldots, y_{k+1}$ be the elements of this set.

We claim that the sets $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k + x_{k+1} \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \} = \\ \{y_i + x_{k+1} \pmod p \ \colon \ i=1,2,\ldots,k+1 \}$$ and $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_k x_k - x_{k+1} \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,k \}= \\ \{y_i-x_{k+1} \pmod p \ \colon \ i=1,2,\ldots,k+1 \}$$ are distinct. For the sake of contradiction suppose that these sets are equal. Comparing their sum modulo $p$ leads to $$y_1+y_2+\ldots+y_{k+1} + (k+1)x_{k+1} \equiv y_1+y_2+\ldots+y_{k+1} - (k+1)x_{k+1} \pmod p,$$ i.e. $$(k+1)x_{k+1}=-(k+1)x_{k+1} \pmod p.$$ Since $p\nmid x_{k+1}$ and $p\nmid k+1$, we have $1\equiv -1 \pmod p$, which is a contradiction since $p$ is odd. This finishes the proof of the claim. $\square$

We now use the claim for $k=p-1$. It follows that the set $$\{\varepsilon_1x_1 + \varepsilon_2 x_2 \ldots +\varepsilon_{p-1} x_{p-1} \pmod{p} \ \colon \ \varepsilon_i \in \{\pm 1\} \text{ for } i=1,2,\ldots,p-1 \}$$ has at least $p$ elements. Thus one of them is $0 \pmod p$ as there are only $p$ remainders modulo $p$. This finishes the proof.

• amazing use of induction and so elegant a proof!Thank you very much
– ShBh
Nov 6, 2017 at 20:26

How about using the Cauchy-Davenport theorem?

Namely, consider the sets $A_i = \{x_i, -x_i\}$. Since $p$ is odd, $|A_i|=2$ for all $i$. Now observe that $$|A_1 + A_2| \geq 2 + 2 - 1 = \min\{p, 3\}$$ One can now show by induction that $$|A_1 + \ldots + A_k| \geq \min\{p, k+1\}$$ Indeed, assuming the hypothesis, the theorem gives us $$|A_1 + \ldots + A_k + A_{k+1}| \geq \min\{p, \min\{p, k+1\} + 2 - 1\}=\min\{p, k+2\}$$ and thus at the end $$|A_1 + \ldots + A_{p-1}|\geq \min\{p,p\}=p$$ so in fact we proved something stronger: we can write any residue modulo $p$ as a sum of the form $\pm x_1 \pm\ldots\pm x_{p-1}$.

• Upon reading the other answer, this seems pretty equivalent, except we used the special case of the theorem to blackbox the explicit inductive step argument. Still, it may help appreciate better what's going on Nov 6, 2017 at 23:11
• in your proof the use of primality of $p$ is very clear.
– ShBh
Nov 7, 2017 at 9:54
• I just want to point out that the fact that $|A_i|=2$ does not follow from the assumption that $p$ is prime but rather that $p$ is odd. Nov 9, 2017 at 17:58
• oops, thanks! corrected. Nov 10, 2017 at 4:28