Given prime $p\ge 11$, $S$ is a subset of $\mathbb{Z}\_p\times\mathbb{Z}\_p$ with $3p-3$ elements. Prove: $S$ has a subset $T$ with $p-1$ elements, such that$\sum\_{x\in T}x\equiv (0,0)\pmod{p}$.



$p-1$ elements in $\mathbb{Z}_p\times\mathbb{Z}_p$ with a sum $(0,0)$
In this post a sum over sets means the additive-combinatorial sum, i.e. $\sum A\_i=\{a\_1+...+a\_i : a\_1 \in A\_1, ..., a\_i \in A\_i\}$.


**Lemma.** Let $(a\_1,a\_2,... ,a\_{2p−2})$ be a sequence of $2p−2$
elements of $\mathbb Z\_p$, where $p$ is a prime. Then either


* there exists a subsequence $A$ of length $p-1$, in which the sum of the elements equals zero, or
* $p$ elements take the same value in the sequence.


**Proof:** We may assume $a\_1 \leq a\_2 \leq ... \leq a\_{2p-2}$. If there are $p$ consecutive values, then we are in the second case, otherwise $a\_1 \neq a\_{p}$, $a\_2 \neq a\_{p+1}$, $...$, $a\_{p-1} \neq a\_{2p-2}$, and we can define the sets $B\_i=\{a\_i,a\_{i+p-1}\}$. By the Cauchy-Davenport theorem, $|\sum B\_i|-1 \geq \sum (|B\_i|-1)$ if $\sum B\_i$ is not the whole $\mathbb Z\_p$, but this is impossible because $\sum (|B\_i|-1) = p-1$. So $0\in ∑B\_i$ and it's possible to pick one element in each $B\_i$ to get a zero sum.


Now we prove the main theorem.


Let $X$ be a sequence where the number of occurences of $x$ is one less than the number of occurences of $x$ in $S$ as the first index, i.e. $|\{i:X\_i=x\}|=|\{y: (x,y)\in S\}|-1$. The sequence has length $2p-3$ if every element appears in $S$ as the first index, and at least $2p-2$ otherwise.


If $X$ has length $2p-3$, we may assume that the elements we choose have first indices $1,2,3...(p-1)$, and we try to find appropriate second indices. Let $Y\_i$ be the set of second indices of the elements of $S$ having first index $i$ ($i \neq 0$). We may assume $\sum |Y\_i| \geq 2p-2$, for otherwise we can choose all the elements $(0,x)$ ($x \neq 0$). Thus $\sum (|Y\_i|-1) \geq p-1$. By the Cauchy-Davenport theorem, $|\sum Y\_i|-1 \geq \sum (|Y\_i|-1)$ if $\sum Y\_i$ is not the whole $\mathbb Z\_p$, but this is impossible because $\sum (|Y\_i|-1) \geq p-1$. So $0\in ∑Y\_i$ and there is an appropriate choice of second indices.


If $X$ has length at least $2p-2$, we may find a $(p-1)$-subsequence $A$ in $X$ that sum to zero, or there are $p$ elements with the same first index (this case is trivial). The sequence $A$ is our choice of first indices, and the point is again trying to find appropriate second indices. Let $Y\_i$ be the set of **k-sums** of second indices of the elements of $S$ having first index $i$ ($i \in A$), where $k$ is the number of occurences of $i$ in $A$. As $k$ is smaller than the number of elements in $S$ having first index $i$ (by the definition of $X$), the set $Y\_i$ has size at least (number of occurences of $i$ in $A$)+1. Now $|\sum Y\_i|-1 \geq \sum (|Y\_i|-1)$ if $\sum Y\_i$ is not the whole $\mathbb{Z} \_p$, but this is impossible because $\sum (|Y\_i|-1) \geq |A| = p-1$. So $0\in ∑Y\_i$ and there is an appropriate choice of second indices.


