A Pigeonhole-Principle from IMO Shortlist.

Question

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

Answer 1

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

Answer 2

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.