2012 USAJMO Problems/Problem 5
Contents
[hide]Problem
For distinct positive integers ,
, define
to be the number of integers
with
such that the remainder when
divided by 2012 is greater than that of
divided by 2012. Let
be the minimum value of
, where
and
range over all pairs of distinct positive integers less than 2012. Determine
.
Solutions
Solution 1
First we'll show that , then we'll find an example
that have
.
Let be the remainder when
is divided by 2012, and let
be defined similarly for
. First, we know that, if
and $bk \nequiv 0 \pmod 2012$ (Error compiling LaTeX. Unknown error_msg), then
and
. This implies that, since
and
,
. Similarly, if
and $ak \nequiv 0 \pmod 2012$ (Error compiling LaTeX. Unknown error_msg) then
, establishing a one-to-one correspondence between the number of
such that
. Thus, if
is the number of
such that
and
, then
. Now I'll show that
.
If , then I'll show you that
. This is actually pretty clear; assume that's not true and set up a congruence relation:
Since
is relatively prime to 2012, it is invertible mod 2012, so we must have
. Since 0 < a, b <2012
a=b
x_k \neq y_k
gcd(k, 2012)=1
x_k \neq 0 \neq y_k
n
n
n \geq \phi(2012) = \phi(503*4) = 1004
S \geq 502$.
To show 502 works, consider$ (Error compiling LaTeX. Unknown error_msg)(a, b)=(1006, 2)k
x_k=0
f(1006, 2)
k = 503, 503*3
x_k = y_k = 1006
f(1006, 2)
x_k \neq 0 \neq y_k
2012-k
x_k > y_k
x_{2012-k} > y_{2012-k}
f(1006, 2)
\frac{1004}{2} = 502 \geq f(1006, 2) \geq S \geq 502
S=502$.
=== Solution 2 ===
Let$ (Error compiling LaTeX. Unknown error_msg)ak \equiv r_{a} \pmod{2012}bk \equiv r_{b} \pmod{2012}
a(2012 - k) \equiv 2012 - r_{a} \pmod{2012}
b(2012 - k) \equiv 2012 - r_{b} \pmod{2012}
k
r_{a} > r_{b}
k
r_{b} > r_{a}
\frac{1}{2}
k
r_{a} \neq r_{b}
r_{a} \neq 0$.
However, the answer is NOT$ (Error compiling LaTeX. Unknown error_msg)\frac{1}{2}(2012) = 1006k
r_{a} = r_{b}
r_{a} = 0$.
So, let's start counting.
If$ (Error compiling LaTeX. Unknown error_msg)ka \equiv 0 \pmod{1006}
a - b \equiv 0 \pmod{1006}
a = 1006
a = b + 1006
1005
k
k
k$at all).
If$ (Error compiling LaTeX. Unknown error_msg)kk = 503
k = 503 \cdot 3
a \equiv 0 \pmod{4}
a \equiv b \pmod{4}
ak \equiv 0 \pmod{2012}
ak \equiv bk \pmod{2012}
a, b < 2012
2
k$.
In total, we have$ (Error compiling LaTeX. Unknown error_msg)2 + 1005 = 1007k
r_{a} = r_{b}
r_{a} = 0
2011 - 1007 = 1004
k
r_{a} \neq r_{b}
r_{a} \neq 0
\frac{1}{2} \cdot 1004 = \boxed{502}$.
Solution by$ (Error compiling LaTeX. Unknown error_msg)\textbf{\underline{Invoker}}ak
bk
a(2012-k)
b(2012-k)
2 \pmod{4}
2012=2^2*503
503
503
2\pmod{4}
2
1006
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)20122012=2^2*503
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.