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)
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)
 
(sujaykazi)

Revision as of 10:48, 21 April 2018

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)

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