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.}$

Solution 2

We consider the Lemma and it's proof as in the above solution.

For every $k$ , let $x_k$ be the number of distinct residues that $a_i + ik$ takes on. Further for each residue $r_i$ , let $n_i$ be the number of times it is achieved by an $a_j + jk$ for $i \in [1, x_k]$ . Note that $\sum_{i = 1}^{x_k} n_i = p.$

The number of pairs $(a_i, a_j)$ s.t $(a_i + ik) - (a_j + jk) \equiv 0$ for a given $k$ is, $\begin{align*} \sum_{i = 1}^{x_k} \binom{n_i}{2} &\ge x_k \binom{(\sum_{i = 1}^{x_k} n_i)/x_k}{2} \\ &= \frac{1}{2}p(\frac{p}{x_k} - 1). \end{align*}$ The first equality is given by a well known theorem, which can be proven by C-S or Jensen's.

Summing over all $k$ , the number of times a pair $(a_i, a_j)$ has $(a_i + ik) - (a_j + jk) \equiv 0$ is, $\begin{align*} \sum_{k = 1}^{p} \frac{1}{2}p(\frac{p}{x_k} - 1). \end{align*}$ Alternatively, every pair $(a_i, a_j)$ has a unique $k$ s.t $(a_i + ik) - (a_j + jk) \equiv 0$ by the Lemma so we double-count as, $\begin{align*} \binom{p}{2} &\ge \sum_{k = 1}^{p} \frac{1}{2}p(\frac{p}{x_k} - 1). \\ 2p - 1 &\ge \sum_{k = 1}^{p} \frac{p}{x_k}. \end{align*}$ By AM-HM inequality, $\begin{align*} \sum_{k = 1}^{p} \frac{p}{x_k} &\ge \frac{p^2}{\sum_{k = 1}^{p} \frac{x_k}{p}} \\ 2p-1 &\ge \frac{p^3}{\sum_{k = 1}^{p} x_k} \\ \sum_{k = 1}^{p}x_k &\ge \frac{p^3}{2p-1} \ge \frac{p^2}{2}. \end{align*}$ So it is clear that $\exists k$ s.t $x_k \ge \frac{p}{2}$ .

~Aaryabhatta1

Page

Toolbox

Search

2018 USAMO Problems/Problem 4

Problem 4

Solution

Solution 2