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 | + | 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 10:44, 24 February 2019
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
Let and
. Notice that this means
and
. Thus, for every value of
where
, there is a value of
where
. Therefore, we merely have to calculate
times the number of values of
for which
and
.
However, the answer is NOT ! This is because we must count the cases where the value of
makes
or where
.
So, let's start counting.
If is even, we have either
or
. So,
or
. We have
even values of
(which is all the possible even values of k, since the two above requirements don't put any bounds on
at all).
If is odd, if
or
, then
or
. Otherwise,
or
, which is impossible to satisfy, given the domain
. So, we have
values of
.
In total, we have values of
which makes
or
, so there are
values of
for which
and
. Thus, by our reasoning above, our solution is
.
Solution by
Solution 2
The key insight in this problem is noticing that when is higher than
,
is lower than
, except at
residues*. Also, they must be equal many times.
. We should have multiples of
. After trying all three pairs and getting
as our answer, we win. But look at the
idea. What if we just took
and plugged it in with
?
We get
.
--Va2010 11:12, 28 April 2012 (EDT)va2010
Solution 3
Say that the problem is a race track with spots. To intersect the most, we should get next to each other a lot so the negation is high. As
, we intersect at a lot of multiples of
.
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.