Problem

Source: USAMO 2018 P4 and JMO 2018 P5, by Ankan Bhattacharya

Tags: USA(J)MO, USAMO, USAJMO, 2018 USAJMO Problem 5, 2018 USAMO Problem 4, Hi, High school olympiad



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 $\tfrac{1}{2} p$ distinct remainders upon division by $p$. Proposed by Ankan Bhattacharya