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 USAJMO Problems/Problem 5"

(→‎Solution)
(→‎Solution)
Line 4: Line 4:
  
 
==Solution==
 
==Solution==
−
Notice that, if <math>a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}</math> for some <math>k\in {1, 2, ..., p},</math> then <math>a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}</math> is false for all other <math>k'\in {1, 2, ..., p}.</math>
+
Notice that, if <math>a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}</math> for some <math>k\in\{1, 2, ..., p\},</math> then <math>a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}</math> is false for all other <math>k'\in {1, 2, ..., p}.</math>
 +
 
 +
<math>\textbf{Lemma: }</math> For fixed <math>i\neq j,</math> where <math>i, j\in\{1, 2, ..., p\},</math> the statement <math>a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}</math> holds for exactly one <math>k\in {1, 2, ..., p}.</math>
 +
 
 +
<math>\textbf{Proof: }</math> Notice that the left side minus the right side is congruent to <math>(a_i - a_j) + (i - j)k</math> modulo <math>p.</math> For this difference to equal <math>0,</math> there is a unique solution for <math>k</math> modulo <math>p</math> given by <math>k\equiv (a_j - a_i)(i - j)^{-1}\text{ (mod } p\text{)},</math> where we have used the fact that every nonzero residue modulo <math>p</math> has a unique multiplicative inverse. Therefore, there is exactly one <math>k\in {1, 2, ..., p}</math> that satisfies <math>a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}</math> for any fixed <math>i\neq j. \textbf{ End Lemma}</math>
 +
 
 +
Suppose that you have <math>p</math> graphs <math>G_1, G_2, ..., G_p,</math> and graph <math>G_k</math> consists of the vertices <math>(i, k)</math> for all <math>1\le i\le p.</math> Within any graph <math>G_k,</math> vertices <math>(i_1, k)</math> and <math>(i_2, k)</math> are connected by an edge if and only if <math>a_{i_1} + i_1k\equiv a_{i_2} + i_2k\text{ (mod } p\text{)}.</math> Notice that the number of disconnected components of any graph <math>G_k</math> equals the number of distinct remainders when divided by <math>p</math> given by the numbers <math>a_1 + k, a_2 + 2k, ..., a_p + pk.</math>
 +
 
 +
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.
 +
 
 +
(sujaykazi)

Revision as of 02:58, 21 April 2018

Problem 5

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

Notice that, if $a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}$ for some $k\in\{1, 2, ..., p\},$ then $a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}$ is false for all other $k'\in {1, 2, ..., p}.$

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

(sujaykazi)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_USAJMO_Problems/Problem_5&oldid=94066"