2018 USAMO Problems/Problem 4

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

Solution

$\textbf{Lemma: }$ For fixed $i\neq j,$ where $i, j\in\{1, 2, ..., p\},$ the statement $a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}$ holds for exactly one $k\in {1, 2, ..., p}.$

$\textbf{Proof: }$ Notice that the left side minus the right side is congruent to $(a_i - a_j) + (i - j)k$ modulo $p.$ For this difference to equal $0,$ there is a unique solution for $k$ modulo $p$ given by $k\equiv (a_j - a_i)(i - j)^{-1}\text{ (mod } p\text{)},$ where we have used the fact that every nonzero residue modulo $p$ has a unique multiplicative inverse. Therefore, there is exactly one $k\in {1, 2, ..., p}$ that satisfies $a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}$ for any fixed $i\neq j. \textbf{ End Lemma}$

Suppose that you have $p$ graphs $G_1, G_2, ..., G_p,$ and graph $G_k$ consists of the vertices $(i, k)$ for all $1\le i\le p.$ Within any graph $G_k,$ vertices $(i_1, k)$ and $(i_2, k)$ are connected by an edge if and only if $a_{i_1} + i_1k\equiv a_{i_2} + i_2k\text{ (mod } p\text{)}.$ Notice that the number of disconnected components of any graph $G_k$ equals the number of distinct remainders when divided by $p$ given by the numbers $a_1 + k, a_2 + 2k, ..., a_p + pk.$

These $p$ graphs together have exactly one edge for every unordered pair of elements of $\{1, 2, ..., p\},$ so they have a total of exactly $\frac{p(p-1)}{2}$ edges. Therefore, there exists at least one graph $G_k$ that has strictly fewer than $\frac{p}{2}$ edges, meaning that it has more than $\frac{p}{2}$ disconnected components. Therefore, the collection of numbers $\{a_i + ik: 1\le i\le p\}$ for this particular value of $k$ has at least $\frac{p}{2}$ distinct remainders modulo $p.$ This completes the proof.

\textbf{Note: This is the same problem as 2018 USAJMO Problem 5.}

(sujaykazi)

Page

Toolbox

Search

2018 USAMO Problems/Problem 4

Problem 4

Solution