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

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