Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2012 USAJMO Problems/Problem 5"

m (→‎Solution 1)
(→‎Solutions)
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>.
 +
 +
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</math> and <math>bk \nequiv 0 \pmod 2012</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>x_k < y_k</math> and <math>ak \nequiv 0 \pmod 2012</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 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>.
  
−
=== Solution 1 ===
+
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 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>.
+
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>.
  
  
−
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>.
+
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>.
  
  
Line 16: Line 25:
  
  
−
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).
+
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).
  
  
−
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>.
+
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>.
+
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 by </math>\textbf{\underline{Invoker}}<math>
  
−
=== Solution 2 ===
+
=== Solution 3 ===
−
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 ===
+
=== 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$.
  
 
==See also==
 
==See also==

Revision as of 18:18, 12 June 2019

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$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_USAJMO_Problems/Problem_5&oldid=106257"