Generalised pigeonhole principle question

Question

Question: Proof Every set $S$ of $20$ integers between $0$ and $188$ contains four distinct elements $x,y,z,w$ such that $189$ divides $(x-y+z-w)$

Hints: Consider their pairwise sums modulo $189$.

My insights: I work out some scratches: $189$'s factors: $\{1,3,7,9,21,27,63\}$

take factor $3$ , it can be sum of $\{1,2\}$,$\{3,0\}$,$\{4,-1\}$, $\{5,-2\}$, $\{6,-3\},\dots , \{188,-185\}$

There is too much information, I can't see their connections (who are the pigeon and who are the holes) and where to apply the hint.

Answer 1

Consider the pair-wise sums of the $20$ selected elements. If any two of these are equal, say $k+l = m+n$, then we can put these directly into the formula as $(k-m+l-n)$ for a result of zero, which is divisible by $189$.

Otherwise we will have $190$ distinct results. However, considering these sums $\bmod 189$, two of these values must be equivalent by the pigeonhole principle and so we can again use these two in the formula to get a number divisible by $189$.

Answer 2

Hint How many pairs of two distinct elements are ?

Hint 2 If two pairs have the same sum modulo $189$, can some of the elements be equal?