2012 USAJMO Problems/Problem 5

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

First we'll show that $S \geq 502$ , then we'll find an example $(a, b)$ that have $f(a, b)=502$ .

Let $x_k$ be the remainder when $ak$ is divided by 2012, and let $y_k$ be defined similarly for $bk$ . First, we know that, if $x_k > y_k$ and $bk \nequiv 0 \pmod 2012$ (Error compiling LaTeX. Unknown error_msg), then $x_{2012-k} \equiv a(2012-k) \equiv 2012-ak \equiv 2012-x_k \pmod 2012$ and $y_{2012-k} \equiv 2012-y_k \pmod 2012$ . This implies that, since $2012 - x_k \neq 0$ and $2012 -y_k \neq 0$ , $x_{2012-k} < y_{2012-k}$ . Similarly, if $x_k < y_k$ and $ak \nequiv 0 \pmod 2012$ (Error compiling LaTeX. Unknown error_msg) then $x_{2012-k} > y_{2012-k}$ , establishing a one-to-one correspondence between the number of $k$ such that $x_k < y_k$ . Thus, if $n$ is the number of $k$ such that $x_k \neq y_k$ and $y_k \neq 0 \neq x_k$ , then $S \geq \frac{1}{2}n$ . Now I'll show that $n \geq 1004$ .

If $gcd(k, 2012)=1$ , then I'll show you that $x_k \neq y_k$ . This is actually pretty clear; assume that's not true and set up a congruence relation: $ak \equiv bk \pmod 2012$ Since $k$ is relatively prime to 2012, it is invertible mod 2012, so we must have $a \equiv b \pmod 2012$ . Since 0 < a, b <2012 $, this means$ a=b $, which the problem doesn't allow, thus contradiction, and$ x_k \neq y_k $. Additionally, if$ gcd(k, 2012)=1 $, then$ x_k \neq 0 \neq y_k $, then based on what we know about$ n $from the previous paragraph,$ n $is at least as large as the number of k relatively prime to 2012. Thus,$ n \geq \phi(2012) = \phi(503*4) = 1004 $. Thus,$ S \geq 502$.

To show 502 works, consider$ (Error compiling LaTeX. Unknown error_msg)(a, b)=(1006, 2) $. For all even$ k $we have$ x_k=0 $, so it doesn't count towards$ f(1006, 2) $. Additionally, if$ k = 503, 503*3 $then$ x_k = y_k = 1006 $, so the only number that count towards$ f(1006, 2) $are the odd numbers not divisible by 503. There are 1004 such numbers. However, for all such odd k not divisible by 503 (so numbers relatively prime to 2012), we have$ x_k \neq 0 \neq y_k $and$ 2012-k $is also relatively prime to 2012. Since under those conditions exactly one of$ x_k > y_k $and$ x_{2012-k} > y_{2012-k} $is true, we have at most 1/2 of the 1004 possible k actually count to$ f(1006, 2) $, so$ \frac{1004}{2} = 502 \geq f(1006, 2) \geq S \geq 502 $, so$ S=502$. === Solution 2 ===

Let$ (Error compiling LaTeX. Unknown error_msg)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$ (Error compiling LaTeX. Unknown error_msg)\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$ (Error compiling LaTeX. Unknown error_msg)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$ (Error compiling LaTeX. Unknown error_msg)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$ (Error compiling LaTeX. Unknown error_msg)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$ (Error compiling LaTeX. Unknown error_msg)\textbf{\underline{Invoker}} $=== Solution 3 === 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$.

--[[User:Va2010|Va2010]] 11:12, 28 April 2012 (EDT)va2010

=== Solution 4 === Say that the problem is a race track with$ (Error compiling LaTeX. Unknown error_msg)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$.

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

Page

Toolbox

Search

2012 USAJMO Problems/Problem 5

Contents

Problem

Solutions

Solution 1

See also