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

Latest revision as of 15:36, 26 June 2023

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 >0$ , 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 $0< x_k < y_k$ 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 $(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 $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 $\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 $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 $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 $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 $\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$ .

--Va2010 11:12, 28 April 2012 (EDT)va2010

Solution 4

Say that the problem is a race track with $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$ .

@@ 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>.
-== Solution ==
+== Solutions ==
-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(mod 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(mod 4)</math> idea. What if we just took <math>2</math> and plugged it in with <math>1006</math>?
+=== 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 >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 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>.
+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 <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>.
+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 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>?
 We get <math>502</math>.
   --[[User:Va2010|Va2010]] 11:12, 28 April 2012 (EDT)va2010
-== Alternate 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>.

2012 USAJMO (Problems • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search