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

Revision as of 01:35, 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}.$

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