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 $\mathbb Z_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$.

At first I thought I forgot what a complete graph meant since this seemed too easy (its obviously going to be killed by some set-addition tactics + cauchy-davenport due to the factor of $p$ in the number of vertices). Oh well, I hope this solution is correct. Partition the graph into $p$ distinct $1000-$gons. In each of the $1000$-gons (call them $P_1, P_2, ..., P_{p}$) designate a start vertex $s_i$ and an end vertex $e_i$ onto $P_i$. Now, I claim that in any of the $1000$-gons $P_i$, if no cycle has the sum of its edges equal to $0 \pmod{p}$ then there exists at least two paths from $s_i$ to $e_i$ which have different sums modulo $p$ of their edges. Suppose there does not exist two such paths. For two vertices $x,y$, denote $e(x,y)$ the value of the edge. We for any three vertices $a,b,c \neq s_i, e_i$ that $e(a,c) \equiv e(a,b) + e(b,c) \pmod{p}$ by considering the two paths $s_i \to a \to c \to e_i$ and $s_1 \to a \to b \to c \to e_i$. However, this tells us that in a triangle contained within $P_i$ which does not contain $s_i$ or $e_i$ that each edge is equal to the sum of the other two edges modulo $p$, which implies that the sum of the edges is $0 \pmod{p}$. If so we are done as there exists a cycle whose sum of edges is divisible by $p$, so it follows that there exist at least $2$ paths from $s_i$ to $e_i$ whose sums modulo $p$ are different. Call the set of these two values $S_i$. Now, consider $S_1 + S_2 + ... + S_p$. By Cauchy-Davenport we have $|S_1 + S_2 + ... + S_p| \ge p$ so it follows that for any integer $k$, we can pick elements out of $S_1, S_2, ..., S_p$ such that their sum is $k \pmod{p}$. Now just pick elements such that their sum is $-\sum_{i=1}^p e(e_i, s_{i+1}) \pmod{p}$ with indices taken modulo $p$ and then consider the cycle which connects $e_i$ to $s_{i+1}$ and within $P_i$ it takes the corresponding path to the element we took out of $S_i$ to connect $s_i$ to $e_i$. It is clear this cycle has sum of its labels divisible by $p$ so we are done.

The method for primes can be extended to $1000n$ as well (without a significant loss in the actual constant, but it seems hard to go below 2 or construct greater than 1).

to use dinoboy's argument about 2 paths of different sums, we only need 5p vertices instead of 1000p, right? s, e, a, b, c. we have se = sa+ac+ce = sa+ab+bc+ce -> ab+bc = ac, and by symmetry we have ab+ac = bc, ac+bc = ab, and this yields the desired result.

Yes, only $5p$ is needed. I think the large value of $1000$ in this problem was used to give away the fact that even weak arguments such as splitting the graph into $p$ parts should work.

Indeed, my construction uses only $3p-3$. dinoboy wrote: I think the large value of $1000$ in this problem was used to give away the fact... Interesting, I actually just interpreted as saying, "throw whatever you can think of at this, you get $O(p)$ vertices". For that reason I thought it was a pretty interesting problem to put on a TST(ST).

Let's denote with $a_1,a_2,\dots,a_{1000p}$ the labels. Since we are dealing with a complete graph we can eliminate some elements from the sum $\sum_{t=1}^{1000p} a_t $. We can do this beacuse we can choose the starting point and since all the vertices are connected with each other then we don't need to worry about the ending point being the starting point. Now by Erdos-Ginzburg-Zif we have that in a sequence of elements taken $\mod p$ we can find $p$ of them such that their sum is divisible by $p$. Thus we can choose from $1000p$, $2p-1$ elements and we will be guaranteed that some of them will have a sum divisible by $p$.

Here is a bad solution for $6p$ that uses unnecessary sledgehammers.

I ate an orange We only solve $p$ odd; the $p = 2$ case is trivial. Everything is in $\mathbb{F}_{p}$. Consider the cycle $T_1 T_2 \ldots T_p$, and let it have sum $T$. Also, let $A_1, A_2, \ldots A_p$ be disjoint cycles such that $A_{i}$ contains the edge $T_{i}T_{i+1}$, and the number of vertices in $A_{i}$ is at most $5$. We also require that the sum of the edges in $A_{i}$ is not $2T_{i}T_{i+1}$ This is possible because, if no such $A_{i}$ existed, then consider three vertices $A,B,C$. We have \[AT_{i} + AT_{i+1} = T_{i}T_{i+1} = AT_{i} + AB + BT_{i+1} \Rightarrow AT_{i+1} = AB + BT_{i+1}\]Similarly, we get $BT_{i+1} = AB + AT_{i+1}$, so $AB = 0$. Similarly, $AC = BC = 0$, so $ABC$ form a cycle with sum $0$, and we are done. Now, define \[B_{i} = A_{i}\backslash \{T_{i}T_{i+1}\} \cup \{T_{i+1}T_{i+2}T_{i+3}\ldots T_{i}\}\]Observe that choosing the sum of $k$ $B_{i}$s (distinct), and then subtracting $(k-1)(T_{1}T_{2}\ldots T_{p-1})$ gives a new cycle. Furthermore, the sum of $B_{i}$ isn't $T$, and we let this sum be $b_i$. Now, it suffices to find $e_1, e_2, \ldots e_p$ such that $e_i = 0, 1$ and \[e_1b_1 + e_2b_2 + \ldots e_pb_p - (e_1 + e_2 + \ldots + e_p-1)T = 0\]\[\Rightarrow e_1(b_1 - T) + e_2(b_2 - T) + \ldots + e_p(b_p - T) = -T\]Since $T\neq 0$ (otherwise we're done), and $b_i\neq T$, by cauchy davenport, there exists such values of $e_i$. We conclude that there exists such a cycle.

v_Enhance wrote: Let $p$ be a prime. Prove that any complete graph with $1000p$ vertices, whose edges are labelled with integers, has a cycle whose sum of labels is divisible by $p$. What? By Erdős–Ginzburg–Ziv theorem we only need to pick $2p-1$ vertices from the $1000p$ vertices and we are done lol

MathLuis wrote: v_Enhance wrote: Let $p$ be a prime. Prove that any complete graph with $1000p$ vertices, whose edges are labelled with integers, has a cycle whose sum of labels is divisible by $p$. What? By Erdős–Ginzburg–Ziv theorem we only need to pick $2p-1$ vertices from the $1000p$ vertices and we are done lol Not everyone know such an obscure theorem like you do.

EulersTurban wrote: Let's denote with $a_1,a_2,\dots,a_{1000p}$ the labels. Since we are dealing with a complete graph we can eliminate some elements from the sum $\sum_{t=1}^{1000p} a_t $. We can do this beacuse we can choose the starting point and since all the vertices are connected with each other then we don't need to worry about the ending point being the starting point. Now by Erdos-Ginzburg-Zif we have that in a sequence of elements taken $\mod p$ we can find $p$ of them such that their sum is divisible by $p$. Thus we can choose from $1000p$, $2p-1$ elements and we will be guaranteed that some of them will have a sum divisible by $p$. MathLuis wrote: v_Enhance wrote: Let $p$ be a prime. Prove that any complete graph with $1000p$ vertices, whose edges are labelled with integers, has a cycle whose sum of labels is divisible by $p$. What? By Erdős–Ginzburg–Ziv theorem we only need to pick $2p-1$ vertices from the $1000p$ vertices and we are done lol Wrong. The labels are on the edges, not the vertices.

Solved with Arjun Gupta. This seems to work for $2p$ vertices too. The value $xy$ for any vertices $x$ and $y$ will denote the label of edge $xy$. Note that for any triangle $abc$, if $bc \neq 0$, then they can be ordered either $a,b,c$ or $a,c,b$ such that $ac \neq ab + bc$ or $ab \neq ac + bc$. Begin with a vertex $A_1$ and designate it the "main" vertex. Inductively iterate the following process $p-1$ times: Pick three other vertices not chosen yet, say $B,C,D$ and suppose $M = A_{2k-1}$ is the main vertex. Then since the cycle sum of $BCD$ is not zero, at least one of the edges is nonzero, say $BC$. Then by the above paragraph, we can order it, say $MBC$ such that $MC \neq MB + BC$. Then, let $B = A_{2k}$ and let $C = A_{2k+1}$ be the new main vertex. This creates a cycle $A_1A_3A_5 \cdots A_{2p-1}$ with a "choice" at each edge, where we can switch to the longer path. If $x_i = A_{2i-1}A_{2i} + A_{2i}A_{2i+1} - A_{2i-1}A_{2i+1}$, then really we just want to add some subset of $x_1, x_2, \cdots, x_{p-1}$ to equal $-A_1A_{2p-1}$. But this is true since we can treat each as a choice between $0$ and $x_i$, so with addition of sets of size two, they must span all values from $0$ to $p-1$ mod $p$ by Cauchy-Davenport (which can be proved by say, cns). So there is some subset we can pick to ensure that we get a cycle with sum zero mod $p$, so we're done. $\blacksquare$

Work modulo $p$. Pick $p-1$ disjoint triangles. If any have sum $0$ then we are done, otherwise for each triangle we can label the vertices $v_{i1},v_{i2},v_{i3}$ in some order such that the weight of $\overline{v_{i2}v_{i3}}$ is not equal to the sum of the weights of $\overline{v_{i1}v_{i2}}$ and $\overline{v_{i1}v_{i3}}$, and let their difference be $d_i \neq 0$. Then form the cycle $v_{12} \to v_{11} \to v_{13} \to v_{22}\to v_{21}\to v_{23}\to \cdots$. By replacing the edges $\overline{v_{i1}v_{i2}},\overline{v_{i1}v_{i3}}$ with $\overline{v_{i2}v_{i3}}$ we increase the sum of weights along this cycle by $d_i$. Considering this possibility for all $i$, we can increase the sum of the weights by any element of $\{0,d_1\}+\cdots+\{0,d_{p-1}\}$, which by Cauchy-Davenport must form a complete residue system, so we can certainly make this cycle have label sum divisible by $p$. $\blacksquare$ Remark: Problem-solving process flowed in the opposite direction of the way the solution is written: consider a large cycle first and notice that by replacing two edges with one we have many different ways to change its label sum. More concretely draw $p-1$ edges and observe that we are done if we can get the difference to be nonzero. Then realize that we have freedom in picking labels (basically we can rotate any triangle around) and can always guarantee this.

A64298347 wrote: EulersTurban wrote: Let's denote with $a_1,a_2,\dots,a_{1000p}$ the labels. Since we are dealing with a complete graph we can eliminate some elements from the sum $\sum_{t=1}^{1000p} a_t $. We can do this beacuse we can choose the starting point and since all the vertices are connected with each other then we don't need to worry about the ending point being the starting point. Now by Erdos-Ginzburg-Zif we have that in a sequence of elements taken $\mod p$ we can find $p$ of them such that their sum is divisible by $p$. Thus we can choose from $1000p$, $2p-1$ elements and we will be guaranteed that some of them will have a sum divisible by $p$. MathLuis wrote: v_Enhance wrote: Let $p$ be a prime. Prove that any complete graph with $1000p$ vertices, whose edges are labelled with integers, has a cycle whose sum of labels is divisible by $p$. What? By Erdős–Ginzburg–Ziv theorem we only need to pick $2p-1$ vertices from the $1000p$ vertices and we are done lol Wrong. The labels are on the edges, not the vertices. Wait why, what if we pick $2p-1$ edges instead? Like, consider a cycle of length $2p-1$, which obviously exists, pick the edges of that cycle and apply that theorem? It works doesnt it?

rama1728 wrote: Wait why, what if we pick $2p-1$ edges instead? Like, consider a cycle of length $2p-1$, which obviously exists, pick the edges of that cycle and apply that theorem? It works doesnt it? The theorem talks about some subset of size $p$ summing to exactly zero, not the entire sum being zero. As mentioned, the labels are on the edges, not the vertices.

We will prove the strengthened version of the problem in which there are $3p-3$ vertices. Consider $p-1$ disjoint triangles in the graph, labeled $T_1, T_2, \dots, T_{p-1}$. If one of these triangles have an edge sum of zero modulo $p$, then we win. Otherwise, label the edges of $T_i$ with labels $a_i$, $b_i$, and $c_i$ such that $a_i+b_i \not\equiv c_i \pmod{p}$. (Such a labeling exists for each triangle, otherwise the sum of the labels for that triangle is evidently zero modulo $p$.) Now take a cycle $\mathcal{C}$ that alternates between the label $c_i$ for each $i$ and an edge that connects $T_i$ to $T_{i+1}$. Let $A_i=\{0, a_i+b_i-c_i\}$ for each $i$. By Cauchy-Davenport modulo $p$, $|A_1+\dots+A_{p-1}| \ge p$, which means that $A_1+\dots+A_{p-1}$ covers all residues modulo $p$. In particular, it contains the residue given by negative of the edge sum in $\mathcal{C}$, which means that we can appropriately replace $c_i$ with $a_i+b_i$ for some subset of the $i$. We conclude.

$p = 2$ can be handled manually. Take three vertices with edge labels $a, b, c$. Claim: Either $a \equiv b \equiv c \equiv 0 \pmod{p}$ or $a + b \not\equiv c \pmod{p}$ for some labelling $a, b, c$. Proof. If $a + b \equiv c, b + c \equiv a, c + a \equiv b \pmod{p}$ then this means that $2(a + b) \equiv a + b + c \equiv 2(a + c)$ so $b \equiv c$. As such, $a \equiv b \equiv c$, which must all be $0$. $\blacksquare$ Then use $3p$ to get $p$ triangles $t_1, t_2, \dots, t_{100}$. Choose an edge $c$ from each triangle such that $a + b \not\equiv c$ for each triangle. Then we can choose between the path with label $c$ and the one with labels $a, b$ in $t$. Suppose that the two paths both go from $x_i$ to $y_i$ in triangle $t_i$. Then take a path that goes $x_i - y_i \to x_{i+1} - y_{i+1} \to \dots$ cyclically where $-$ indicates choosing between one of the two paths. Claim: Let $S$ be a set of $p$ occurences of $(a_i, b_i) \in {\mathbb F}_p^2, a_i \ne b_i$ for $1 \le i \le p$ and let $r$ be a residue in ${\mathbb F}_p$. Then there exists a choice function $c$ on $S$ such that the sum of the choices is $r$. Proof. We claim that if $|S| = d$ for $0 \le d \le p$, then there are at least $d$ possible residues over all $2^d$ choice functions. Induct with base case $d = 0$. Then for the next case, WLOG we can consider choosing between $0$ and $t, t \not\equiv 0$. Suppose this keeps $S$ the same size, then $a \in S \implies a + t \in S$. Since $t \not\equiv 0$, this implies $S = {\mathbb F}_p$ which suffices. $\blacksquare$ Then take a choice function such that the sum of the choices for each $x_i - y_i$ and the sum over all labels $y_i \to x_{i+1}$ is $0 \pmod{p}$.