Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2018 USAMO Problems/Problem 4"

(Created page with "==Problem 4== Let <math>p</math> be a prime, and let <math>a_1, \dots, a_p</math> be integers. Show that there exists an integer <math>k</math> such that the numbers <cmath>a_...")
 
(→‎Solution 2)
 
(2 intermediate revisions by 2 users not shown)
Line 12: Line 12:
 
These <math>p</math> graphs together have exactly one edge for every unordered pair of elements of <math>\{1, 2, ..., p\},</math> so they have a total of exactly <math>\frac{p(p-1)}{2}</math> edges. Therefore, there exists at least one graph <math>G_k</math> that has strictly fewer than <math>\frac{p}{2}</math> edges, meaning that it has more than <math>\frac{p}{2}</math> disconnected components. Therefore, the collection of numbers <math>\{a_i + ik: 1\le i\le p\}</math> for this particular value of <math>k</math> has at least <math>\frac{p}{2}</math> distinct remainders modulo <math>p.</math> This completes the proof.
 
These <math>p</math> graphs together have exactly one edge for every unordered pair of elements of <math>\{1, 2, ..., p\},</math> so they have a total of exactly <math>\frac{p(p-1)}{2}</math> edges. Therefore, there exists at least one graph <math>G_k</math> that has strictly fewer than <math>\frac{p}{2}</math> edges, meaning that it has more than <math>\frac{p}{2}</math> disconnected components. Therefore, the collection of numbers <math>\{a_i + ik: 1\le i\le p\}</math> for this particular value of <math>k</math> has at least <math>\frac{p}{2}</math> distinct remainders modulo <math>p.</math> This completes the proof.
  
−
\textbf{Note: This is the same problem as 2018 USAJMO Problem 5.}
+
<math>\textbf{Note: This is the same problem as 2018 USAJMO Problem 5.}</math>
  
−
(sujaykazi)
+
==Solution 2==
 +
We consider the Lemma and it's proof as in the above solution.
 +
 
 +
For every <math>k</math>, let <math>x_k</math> be the number of distinct residues that <math>a_i + ik</math> takes on. Further for each residue <math>r_i</math>, let <math>n_i</math> be the number of times it is achieved by an <math>a_j + jk</math> for <math>i \in [1, x_k]</math>. Note that <math>\sum_{i = 1}^{x_k} n_i = p.</math>
 +
 
 +
The number of pairs <math>(a_i, a_j)</math> s.t <math>(a_i + ik) - (a_j + jk) \equiv 0</math> for a given <math>k</math> is,
 +
<cmath>\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*}</cmath>
 +
The first equality is given by a well known theorem, which can be proven by C-S or Jensen's.
 +
 
 +
Summing over all <math>k</math>, the number of times a pair <math>(a_i, a_j)</math> has <math>(a_i + ik) - (a_j + jk) \equiv 0</math> is,
 +
<cmath>\begin{align*}
 +
\sum_{k = 1}^{p} \frac{1}{2}p(\frac{p}{x_k} - 1).
 +
\end{align*}</cmath>
 +
Alternatively, every pair <math>(a_i, a_j)</math> has a unique <math>k</math> s.t <math>(a_i + ik) - (a_j + jk) \equiv 0</math> by the Lemma so we double-count as,
 +
<cmath>\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*}</cmath>
 +
By AM-HM inequality,
 +
<cmath>\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*}</cmath>
 +
So it is clear that <math>\exists k</math> s.t <math>x_k \ge \frac{p}{2}</math>.
 +
 
 +
~Aaryabhatta1

Latest revision as of 20:46, 20 March 2023

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_USAMO_Problems/Problem_4&oldid=191134"