USAMO 2018 — Days 1 and 2 Question 4

Let $p$ be prime and $a_1,\ldots,a_p$ be integers. Prove that some integer $k$ makes $a_1+k,a_2+2k,\ldots,a_p+pk$ have at least $p/2$ distinct remainders modulo $p$.

Proposed by Ankan Bhattacharya. Source: Evan Chen’s third-party compilation, not an official publication. One editorial point; manual grading only.