Difference between revisions of "2012 USAJMO Problems/Problem 5"

(Alternate, formal argument)
Line 15: Line 15:
  
 
{{USAJMO newbox|year=2012|num-b=4|num-a=6}}
 
{{USAJMO newbox|year=2012|num-b=4|num-a=6}}
 +
{{MAA Notice}}

Revision as of 17:10, 3 July 2013

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(mod 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(mod 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 (ProblemsResources)
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