Problem: Let $p$ be a prime.
Prove that in a complete graph with $1000p$ vertices
whose edges are labelled with integers,
one can find a cycle whose sum of labels is divisible by $p$.

Solution: Select $p-1$ disjoint triangles arbitrarily.  If any of these triangles have $0$ sum modulo $p$ we are done.  Otherwise, we may label the vertices $u_i$, $x_i$, and $v_i$ (where $1 \le i \le p-1$) in such a way that $u_ix_i + x_iv_i \neq u_iv_i$.

Let $A_i = \left\{ u_ix_i+x_iv_i, u_iv_i \right\}$.  We can show that $\left\lvert A_1 + A_2 + \dots + A_t \right\rvert \ge \min \left\{ p,t+1 \right\}$ for each $1 \le t \le p-1$, by using induction on $t$ alongside Cauchy-Davenport.  So, $A_1 + A_2 + \dots + A_{p-1}$ spans all of $\ZZ_p$.  All that's left to do is join the triangles together to form a cycle, and then delete either $u_ix_i,x_iv_i$ or $u_iv_i$ from each triangle in such a way that the final sum is $0$ mod $p$.