Difference between revisions of "2012 USAJMO Problems/Problem 5"
m (fixing bad LaTeX) |
|||
Line 3: | Line 3: | ||
For distinct positive integers <math>a</math>, <math>b < 2012</math>, define <math>f(a,b)</math> to be the number of integers <math>k</math> with <math>1 \le k < 2012</math> such that the remainder when <math>ak</math> divided by 2012 is greater than that of <math>bk</math> divided by 2012. Let <math>S</math> be the minimum value of <math>f(a,b)</math>, where <math>a</math> and <math>b</math> range over all pairs of distinct positive integers less than 2012. Determine <math>S</math>. | For distinct positive integers <math>a</math>, <math>b < 2012</math>, define <math>f(a,b)</math> to be the number of integers <math>k</math> with <math>1 \le k < 2012</math> such that the remainder when <math>ak</math> divided by 2012 is greater than that of <math>bk</math> divided by 2012. Let <math>S</math> be the minimum value of <math>f(a,b)</math>, where <math>a</math> and <math>b</math> range over all pairs of distinct positive integers less than 2012. Determine <math>S</math>. | ||
− | == Solution == | + | == Solutions == |
+ | |||
+ | === 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>. | ||
+ | |||
+ | |||
+ | However, the answer is NOT <math>\frac{1}{2}(2012) = 1006</math>! This is because we must count the cases where the value of <math>k</math> makes <math>r_{a} = r_{b}</math> or where <math>r_{a} = 0</math>. | ||
+ | |||
+ | |||
+ | So, let's start counting. | ||
+ | |||
+ | |||
+ | If <math>k</math> is even, we have either <math>a \equiv 0 \pmod{1006}</math> or <math>a - b \equiv 0 \pmod{1006}</math>. So, <math>a = 1006</math> or <math>a = b + 1006</math>. We have <math>1005</math> even values of <math>k</math> (which is all the possible even values of k, since the two above requirements don't require <math>k</math> at all). | ||
+ | |||
+ | |||
+ | If <math>k</math> is odd, if <math>k = 503</math> or <math>k = 503 \cdot 3</math>, then <math>a \equiv 0 \pmod{4}</math> or <math>a \equiv b \pmod{4}</math>. Otherwise, <math>ak \equiv 0 \pmod{2012}</math> or <math>ak \equiv bk \pmod{2012}</math>, which is impossible to satisfy, given the domain <math>a, b < 2012</math>. So, we have <math>2</math> values of <math>k</math>. | ||
+ | |||
+ | |||
+ | In total, we have <math>2 + 1005 = 1007</math> values of <math>k</math> which makes <math>r_{a} = r_{b}</math> or <math>r_{a} = 0</math>, so there are <math>2011 - 1007 = 1004</math> values of <math>k</math> for which <math>r_{a} \neq r_{b}</math> and <math>r_{a} \neq 0</math>. Thus, by our reasoning above, our solution is <math>\frac{1}{2} \cdot 1004 = \boxed{502}</math>. | ||
+ | |||
+ | |||
+ | Solution by <math>\textbf{\underline{Invoker}}</math> | ||
+ | |||
+ | |||
+ | === Solution 2 === | ||
The key insight in this problem is noticing that when <math>ak</math> is higher than <math>bk</math>, <math>a(2012-k)</math> is lower than <math> b(2012-k)</math>, except at <math>2 \pmod{4}</math> residues*. Also, they must be equal many times. <math>2012=2^2*503</math>. We should have multiples of <math>503</math>. After trying all three pairs and getting <math>503</math> as our answer, we win. But look at the <math>2\pmod{4}</math> idea. What if we just took <math>2</math> and plugged it in with <math>1006</math>? | The key insight in this problem is noticing that when <math>ak</math> is higher than <math>bk</math>, <math>a(2012-k)</math> is lower than <math> b(2012-k)</math>, except at <math>2 \pmod{4}</math> residues*. Also, they must be equal many times. <math>2012=2^2*503</math>. We should have multiples of <math>503</math>. After trying all three pairs and getting <math>503</math> as our answer, we win. But look at the <math>2\pmod{4}</math> idea. What if we just took <math>2</math> and plugged it in with <math>1006</math>? | ||
We get <math>502</math>. | We get <math>502</math>. | ||
--[[User:Va2010|Va2010]] 11:12, 28 April 2012 (EDT)va2010 | --[[User:Va2010|Va2010]] 11:12, 28 April 2012 (EDT)va2010 | ||
− | == | + | === Solution 3 === |
Say that the problem is a race track with <math>2012</math> spots. To intersect the most, we should get next to each other a lot so the negation is high. As <math>2012=2^2*503</math>, we intersect at a lot of multiples of <math>503</math>. | Say that the problem is a race track with <math>2012</math> spots. To intersect the most, we should get next to each other a lot so the negation is high. As <math>2012=2^2*503</math>, we intersect at a lot of multiples of <math>503</math>. | ||
Revision as of 18:41, 23 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 case where
, there is a case 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 require
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.