USAMO 2018 Problem 4

Let \(p\) be a prime, and let \(a_1, \dots, a_p\) be integers. Show that there exists an integer \(k\) such that the numbers \[a_1 + k, a_2 + 2k, \dots, a_p + pk\] produce at least \(\frac{p}{2}\) distinct remainders upon division by \(p\).

========================================

Proof:

The statement holds trivially for \(p=2\). Otherwise, we count collisions defined by \(a_i+ik=a_j+jk\) for \(i\ne j\) and  \(k\in[0,p-1]\). It occurs exactly once for each pair of \((i,j)\) because \(p\) is prime. So there are a total of \(\frac{p(p-1)}{2}\) collisions, and hence some \(k\) sees at most \(\frac{p-1}{2}\) of them. But if given \(k\) \[a_1 + k, a_2 + 2k, \dots, a_p + pk\] produces less than \(\frac{p}{2}\) distinct remainders, i.e. at most \(\frac{p-1}{2}\) remainders, then the minimum number of collisions occur when the remainders form \(\frac{p-1}{2}\) clusters where \(\frac{p-3}{2}\) of them has two elements and the last one has three. This gives \(\frac{p-3}{2}+3=\frac{p+3}{2}\) collisions. So there exists a \(k\) that sees at least \(\frac{p}{2}\) distinct remainders.
Q.E.D.