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

(→‎Solution)
m (fixing bad LaTeX)
Line 4: Line 4:
  
 
== Solution ==
 
== Solution ==
−
The key insight in this problem is noticing that when <math>ak</math> is higher than <math>bk</math>, <math>a(2012-k)</math> is lower than <math> b(2012-k)</math>, except at <math>2 \pmod{4}</math> residues*. Also, they must be equal many times. <math>2012=2^2*503</math>. We should have multiples of <math>503</math>. After trying all three pairs and getting <math>503</math> as our answer, we win. But look at the <math>2\pmod{4})</math> idea. What if we just took <math>2</math> and plugged it in with <math>1006</math>?
+
The key insight in this problem is noticing that when <math>ak</math> is higher than <math>bk</math>, <math>a(2012-k)</math> is lower than <math> b(2012-k)</math>, except at <math>2 \pmod{4}</math> residues*. Also, they must be equal many times. <math>2012=2^2*503</math>. We should have multiples of <math>503</math>. After trying all three pairs and getting <math>503</math> as our answer, we win. But look at the <math>2\pmod{4}</math> idea. What if we just took <math>2</math> and plugged it in with <math>1006</math>?
 
We get <math>502</math>.
 
We get <math>502</math>.
 
  --[[User:Va2010|Va2010]] 11:12, 28 April 2012 (EDT)va2010
 
  --[[User:Va2010|Va2010]] 11:12, 28 April 2012 (EDT)va2010

Revision as of 12:34, 18 January 2014

Problem

For distinct positive integers $a$, $b < 2012$, define $f(a,b)$ to be the number of integers $k$ with $1 \le k < 2012$ such that the remainder when $ak$ divided by 2012 is greater than that of $bk$ divided by 2012. Let $S$ be the minimum value of $f(a,b)$, where $a$ and $b$ range over all pairs of distinct positive integers less than 2012. Determine $S$.

Solution

The key insight in this problem is noticing that when $ak$ is higher than $bk$, $a(2012-k)$ is lower than $b(2012-k)$, except at $2 \pmod{4}$ residues*. Also, they must be equal many times. $2012=2^2*503$. We should have multiples of $503$. After trying all three pairs and getting $503$ as our answer, we win. But look at the $2\pmod{4}$ idea. What if we just took $2$ and plugged it in with $1006$? We get $502$. 

--Va2010 11:12, 28 April 2012 (EDT)va2010

Alternate Solution

Say that the problem is a race track with $2012$ spots. To intersect the most, we should get next to each other a lot so the negation is high. As $2012=2^2*503$, we intersect at a lot of multiples of $503$.

See also

2012 USAJMO (Problems • Resources)
Preceded by
Problem 4 		Followed by
Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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