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"
Line 7: Line 7:
 
=== Solution 1 ===
 
=== Solution 1 ===
  
−
Let <math>ak \equiv r_{a} \pmod{2012}</math> and <math>bk \equiv r_{b} \pmod{2012}</math>. Notice that this means <math>a(2012 - k) \equiv 2012 - r_{a} \pmod{2012}</math> and <math>b(2012 - k) \equiv 2012 - r_{b} \pmod{2012}</math>. Thus, for every case where <math>r_{a} > r_{b}</math>, there is a case where <math>r_{b} > r_{a}</math>. Therefore, we merely have to calculate <math>\frac{1}{2}</math> times the number of values of <math>k</math> for which <math>r_{a} \neq r_{b}</math> and <math>r_{a} \neq 0</math>.
+
Let <math>ak \equiv r_{a} \pmod{2012}</math> and <math>bk \equiv r_{b} \pmod{2012}</math>. Notice that this means <math>a(2012 - k) \equiv 2012 - r_{a} \pmod{2012}</math> and <math>b(2012 - k) \equiv 2012 - r_{b} \pmod{2012}</math>. Thus, for every value of <math>k</math> where <math>r_{a} > r_{b}</math>, there is a value of <math>k</math> where <math>r_{b} > r_{a}</math>. Therefore, we merely have to calculate <math>\frac{1}{2}</math> times the number of values of <math>k</math> for which <math>r_{a} \neq r_{b}</math> and <math>r_{a} \neq 0</math>.
  
  

Revision as of 09:44, 24 February 2019

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$.

Solutions

Solution 1

Let $ak \equiv r_{a} \pmod{2012}$ and $bk \equiv r_{b} \pmod{2012}$. Notice that this means $a(2012 - k) \equiv 2012 - r_{a} \pmod{2012}$ and $b(2012 - k) \equiv 2012 - r_{b} \pmod{2012}$. Thus, for every value of $k$ where $r_{a} > r_{b}$, there is a value of $k$ where $r_{b} > r_{a}$. Therefore, we merely have to calculate $\frac{1}{2}$ times the number of values of $k$ for which $r_{a} \neq r_{b}$ and $r_{a} \neq 0$.


However, the answer is NOT $\frac{1}{2}(2012) = 1006$! This is because we must count the cases where the value of $k$ makes $r_{a} = r_{b}$ or where $r_{a} = 0$.


So, let's start counting.


If $k$ is even, we have either $a \equiv 0 \pmod{1006}$ or $a - b \equiv 0 \pmod{1006}$. So, $a = 1006$ or $a = b + 1006$. We have $1005$ even values of $k$ (which is all the possible even values of k, since the two above requirements don't put any bounds on $k$ at all).


If $k$ is odd, if $k = 503$ or $k = 503 \cdot 3$, then $a \equiv 0 \pmod{4}$ or $a \equiv b \pmod{4}$. Otherwise, $ak \equiv 0 \pmod{2012}$ or $ak \equiv bk \pmod{2012}$, which is impossible to satisfy, given the domain $a, b < 2012$. So, we have $2$ values of $k$.


In total, we have $2 + 1005 = 1007$ values of $k$ which makes $r_{a} = r_{b}$ or $r_{a} = 0$, so there are $2011 - 1007 = 1004$ values of $k$ for which $r_{a} \neq r_{b}$ and $r_{a} \neq 0$. Thus, by our reasoning above, our solution is $\frac{1}{2} \cdot 1004 = \boxed{502}$.


Solution by $\textbf{\underline{Invoker}}$


Solution 2

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

Solution 3

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=103797"