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

(Solution)
(Solution)
Line 4: Line 4:
  
 
== Solution ==
 
== Solution ==
The key insight in this problemo is noticing that when ak is higher then bk, a(2012-k) is lower than b(2012-k), except at 2(mod 4) residues*. Also, they must be equal quite a lot. 2012=2^2*503. We should have multiples of 503. After trying all three pairs and getting 503 as our answer, we win.
+
The key insight in this problemo is noticing that when ak is higher then bk, a(2012-k) is lower than b(2012-k), except at 2(mod 4) residues*. Also, they must be equal quite a lot. 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.
*Addenum: If we try 1006 and 503, 1006 is almost never in the front seat --[[User:Va2010|Va2010]] 11:12, 28 April 2012 (EDT)va2010
+
We get 502.
 +
--[[User:Va2010|Va2010]] 11:12, 28 April 2012 (EDT)va2010
 +
 
 
== Alternate, formal argument==
 
== Alternate, formal argument==
 
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.
 
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.

Revision as of 10:43, 28 April 2012

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 problemo is noticing that when ak is higher then bk, a(2012-k) is lower than b(2012-k), except at 2(mod 4) residues*. Also, they must be equal quite a lot. 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, formal argument

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
Invalid username
Login to AoPS