Difference between revisions of "2012 USAJMO Problems/Problem 5"
Impromptua (talk | contribs) m (→Solution 1) |
|||
(7 intermediate revisions by 3 users not shown) | |||
Line 4: | Line 4: | ||
== Solutions == | == Solutions == | ||
+ | === Solution 1 === | ||
+ | First we'll show that <math>S \geq 502</math>, then we'll find an example <math>(a, b)</math> that have <math>f(a, b)=502</math>. | ||
− | === Solution | + | Let <math>x_k</math> be the remainder when <math>ak</math> is divided by 2012, and let <math>y_k</math> be defined similarly for <math>bk</math>. First, we know that, if <math>x_k > y_k >0</math>, then <math>x_{2012-k} \equiv a(2012-k) \equiv 2012-ak \equiv 2012-x_k \pmod {2012}</math> and <math>y_{2012-k} \equiv 2012-y_k \pmod {2012}</math>. This implies that, since <math>2012 - x_k \neq 0</math> and <math>2012 -y_k \neq 0</math>, <math>x_{2012-k} < y_{2012-k}</math>. Similarly, if <math>0< x_k < y_k</math> then <math>x_{2012-k} > y_{2012-k}</math>, establishing a one-to-one correspondence between the number of <math>k</math> such that <math>x_k < y_k</math>. Thus, if <math>n</math> is the number of <math>k</math> such that <math>x_k \neq y_k</math> and <math>y_k \neq 0 \neq x_k </math>, then <math>S \geq \frac{1}{2}n</math>. Now I'll show that <math>n \geq 1004</math>. |
+ | |||
+ | If <math>gcd(k, 2012)=1</math>, then I'll show you that <math>x_k \neq y_k</math>. This is actually pretty clear; assume that's not true and set up a congruence relation: | ||
+ | <cmath>ak \equiv bk \pmod {2012}</cmath> | ||
+ | Since <math>k</math> is relatively prime to 2012, it is invertible mod 2012, so we must have <math>a \equiv b \pmod {2012}</math>. Since <math>0 < a, b <2012</math>, this means <math>a=b</math>, which the problem doesn't allow, thus contradiction, and <math>x_k \neq y_k</math>. Additionally, if <math>gcd(k, 2012)=1</math>, then <math>x_k \neq 0 \neq y_k</math>, then based on what we know about <math>n</math> from the previous paragraph, <math>n</math> is at least as large as the number of k relatively prime to 2012. Thus, <math>n \geq \phi(2012) = \phi(503*4) = 1004</math>. Thus, <math>S \geq 502</math>. | ||
+ | |||
+ | To show 502 works, consider <math>(a, b)=(1006, 2)</math>. For all even <math>k</math> we have <math>x_k=0</math>, so it doesn't count towards <math>f(1006, 2)</math>. Additionally, if <math>k = 503, 503*3</math> then <math>x_k = y_k = 1006</math>, so the only number that count towards <math>f(1006, 2)</math> 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 <math>x_k \neq 0 \neq y_k</math> and <math>2012-k</math> is also relatively prime to 2012. Since under those conditions exactly one of <math>x_k > y_k</math> and <math>x_{2012-k} > y_{2012-k}</math> is true, we have at most 1/2 of the 1004 possible k actually count to <math>f(1006, 2)</math>, so <math>\frac{1004}{2} = 502 \geq f(1006, 2) \geq S \geq 502</math>, so <math>S=502</math>. | ||
+ | |||
+ | === Solution 2 === | ||
− | 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>. |
Line 16: | Line 26: | ||
− | 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 | + | 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 <math>k</math>, since the two above requirements don't put any bounds on <math>k</math> at all). |
Line 27: | Line 37: | ||
Solution by <math>\textbf{\underline{Invoker}}</math> | Solution by <math>\textbf{\underline{Invoker}}</math> | ||
− | + | === Solution 3 === | |
− | === Solution | ||
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 | + | === Solution 4 === |
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>. | ||
Latest revision as of 16:36, 26 June 2023
Contents
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
, then
and
. This implies that, since
and
,
. Similarly, if
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
, this means
, which the problem doesn't allow, thus contradiction, and
. Additionally, if
, then
, then based on what we know about
from the previous paragraph,
is at least as large as the number of k relatively prime to 2012. Thus,
. Thus,
.
To show 502 works, consider . For all even
we have
, so it doesn't count towards
. Additionally, if
then
, so the only number that count towards
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
and
is also relatively prime to 2012. Since under those conditions exactly one of
and
is true, we have at most 1/2 of the 1004 possible k actually count to
, so
, so
.
Solution 2
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
, 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 3
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 4
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.