Pigeonhole principle with congruence

Question

Let $S\subset \mathbb{Z}/n\mathbb{Z}$ where $n$ is even and $n\geq2$, and $\mid S\mid\geq n/2$. Show that there exist $x, y\in S$ with $x+y\equiv 0 \pmod{n}$

The hint is the pigeonhole principle and it is my first time heard about it. I read the wiki page and some posts from the form. The definitions seem very clear, but I still don't know how to use it...

Any help will be great.

Answer 1

Let $n=2k$

Then $\Bbb{Z}/n\Bbb{Z}=\{[0],[1],...,[k],[k+1],...,[2k-1]\}$ and $|S| \geq k$

If $S$ contains the element $[0]$ or $[k]$ then take $x=y=0$ or $x=y=k$

If $S$ does not contain $[0]$ and $[k]$ then it is a subset of the set $\Bbb{Z}/n\Bbb{Z} \setminus \{[0],[k]\}$ which contains $2k-2$ elements.

Take as pigeonholes the couples $([s],[2k-s]), s=1,...,k-1$

So we have $k-1$ such couples and $|S| \geq k$ so by pigeonhole principle $S$ must have at least two elements $[s],[2k-s]$

Answer 2

Suppose $S$ does not contain $\frac{n}{2}$. (Or else the problem is trivial). Proceed by contradiction and suppose that no element in $S$ had an inverse. (Using the group theory definition here). But this is a contradiction, since every element in a group has a unique inverse and half of the elements of $\mathbb{Z}/n\mathbb{Z}$ are in $S$. (If every element had a unique inverse not in $S$ there would be more than $n$ elements of $\mathbb{Z}/n\mathbb{Z}$).