Difference between revisions of "2020 USOJMO Problems/Problem 5"

Revision as of 12:34, 7 July 2020

Problem

Suppose that $(a_1,b_1),$ $(a_2,b_2),$ $\dots,$ $(a_{100},b_{100})$ are distinct ordered pairs of nonnegative integers. Let $N$ denote the number of pairs of integers $(i,j)$ satisfying $1\leq i<j\leq 100$ and $|a_ib_j-a_jb_i|=1$ . Determine the largest possible value of $N$ over all possible choices of the $100$ ordered pairs.

Solution

Call the pair $(i, j)$ good if $1\leq i < j \leq 100$ and $|a_ib_j-a_jb_i|=1$ . Note that we can reorder the pairs $(a_1, b_1), (a_2, b_2), \ldots, (a_{100}, b_{100})$ without changing the number of good pairs. Thus, we can reorder them so that $a_1\leq a_2\leq\ldots\leq a_{100}$ . Furthermore, reorder them so that if $a_i=a_j$ for some $i<j$ , then $b_i<b_j$ .

Now I claim the maximum value of $N$ is $\boxed{197}$ . First, we will show $N\leq 197$ .

The key claim is that for any fixed integer $m$ , $1\leq m \leq 100$ , then there are at most 2 values of $i$ with $1\leq i<m$ with the pair $(i, m)$ good. We will prove this with contradiction.

Assume there are 3 integers $i$ , $j$ , and $k$ that are less than $m$ , such that $(i, m)$ , $(j, m)$ , and $(k, m)$ are all good. Note that $gcd(a_m, b_m)$ divides $a_ib_m-a_mb_i=\pm 1$ , so $gcd(a_m, b_m)=1$ . From $a_ib_m-a_mb_i=\pm 1$ , we have $a_ib_m\equiv \pm 1 \mod a_m$ Similarly, $a_jb_m\equiv \pm 1 \mod a_m$ $a_kb_m\equiv \pm 1 \mod a_m$

From $gcd(a_m, b_m)=1$ we have $a_i\equiv \pm a_j \equiv \pm a_k \mod a_m$

But since $i$ , $j$ , and $k$ are less than $m$ , from our reordering we have $0\leq a_i<a_m$ , $0\leq a_j<a_m$ , and $0\leq a_k<a_m$ . Thus our congruence gives us that $a_j=a_i$ or $a_j=a_m-a_i$ , and similar for $a_k$ . Thus at least two of $a_i, a_j, a_k$ are equal. WLOG let them be $a_i$ and $a_j$ . Now we have 4 cases.

Case 1: $a_m>2$

We have $a_ib_m-a_mb_i=\pm 1$ and $a_jb_m-a_mb_j=\pm 1$ , so since $a_i=a_j$ we can subtract the two equations to get $a_mb_i-a_mb_j$ equals $\pm 2, 0$ . But $a_m>2$ , so $|a_m(b_i-b_j)|\leq 2$ implies that $b_i=b_j$ . But all pairs are distinct and $a_i=a_j$ , so this is a contradiction.

Case 2: $a_m=2$

We have 2 subcases.

Subcase 2a: $a_i\equiv a_j\equiv a_k\equiv 1 \mod a_m$

Clearly we must have $a_i=a_j=a_k=1$ in this case, as all 3 variables are less than $a_m=2$ . Then $1\cdot b_m-a_mb_i=\pm 1$ , $1\cdot b_m-a_mb_j=\pm 1$ , and $1\cdot b_m-a_mb_k=\pm 1$ . So at least 2 of $b_i$ , $b_j$ , and $b_k$ must be equal, but this contradicts the fact that all pairs $(a_x, b_x)$ are distinct.

Subcase 2b: $a_i\equiv a_j\equiv a_k\equiv 0 \mod a_m$

$a_i$ must be even in this case, but since $a_m$ is also even then $a_ib_m-a_mb_i$ must be even, which contradicts $|a_ib_m-a_mb_i|=1$ .

Case 3: $a_m=1$

We must have $a_i=0,1$ , and similarly for $a_j$ and $a_k$ . Thus at least 2 of the 3 must be equal. Now we have 2 subcases again.

Subcase 3a: 2 of the 3 are equal to 0

WLOG let $a_i=a_j=0$ . Then $a_ib_m-a_mb_i=\pm 1$ and $a_m=1$ so $b_i=\pm 1$ . Since $b_i$ is nonnegative, $b_i=1$ . Similarly $b_j=1$ , but all pairs are distinct so we have a contradiction.

Subcase 3b: 2 of the 3 are equal to 1

WLOG let $a_i=a_j=0$ . Then $a_ib_m-a_mb_i=\pm 1$ , so $b_m-b_i=\pm 1$ . But $i<m$ and $a_i=a_m=1$ , so by our ordering of the pairs we have $b_i<b_m$ so $b_m-b_i=1$ . But similarly $b_m-b_j=1$ , so $b_i=b_j$ , which is a contradiction to all pairs being distinct.

Case 4: $a_m=0$

We must have $a_i=0$ , since $0\leq a_i\leq a_m=0$ . Thus $a_ib_m-a_mb_i=0$ , but $|a_ib_m-a_mb_i|=1$ , contradiction. $\blacksquare$

Thus our claim is proved. Now for $m=1$ , there is clearly no $i$ with $1\leq i < m \leq 100$ and $(i, m)$ good. For $m=2$ , there is at most one value of i with $1\leq i < m \leq 100$ and $(i, m)$ good (namely, this is when $i=1$ ). By our claim, for all $2<m\leq 100$ there are at most 2 values of $i$ with $1\leq i < m \leq 100$ and $(i, m)$ good, so adding these up gives at most $2\cdot 98+1=197$ good pairs. Now we will show that 197 good pairs is achievable.

The sequence $(1,1), (1,2), (2,3),\ldots ,(99,100)$ has 197 good pairs - namely, $(1, n)$ is good for all $1<n\leq 100$ , and $(i, i+1)$ is good for all $1<i<100$ . This adds up for a total of 197 good pairs, so we are done. $\blacksquare$

~MortemEtInteritum

@@ Line 52: / Line 52: @@
 Thus our claim is proved. Now for <math>m=1</math>, there is clearly no <math>i</math> with <math>1\leq i < m \leq 100</math> and <math>(i, m)</math> good. For <math>m=2</math>, there is at most one value of i with <math>1\leq i < m \leq 100</math> and <math>(i, m)</math> good (namely, this is when <math>i=1</math>). By our claim, for all <math>2<m\leq 100</math> there are at most 2 values of <math>i</math> with <math>1\leq i < m \leq 100</math> and <math>(i, m)</math> good, so adding these up gives at most <math>2\cdot 98+1=197</math> good pairs. Now we will show that 197 good pairs is achievable.
-The sequence <math>(1,1) (1,2) (2,3)...(99,100)</math> has 197 good pairs - namely, <math>(1, n)</math> is good for all <math>1<n\leq 100</math>, and <math>(i, i+1)</math> is good for all <math>1<i<100</math>. This adds up for a total of 197 good pairs, so we are done. <math>\blacksquare</math>
+The sequence <math>(1,1), (1,2), (2,3),\ldots ,(99,100)</math> has 197 good pairs - namely, <math>(1, n)</math> is good for all <math>1<n\leq 100</math>, and <math>(i, i+1)</math> is good for all <math>1<i<100</math>. This adds up for a total of 197 good pairs, so we are done. <math>\blacksquare</math>
 ~MortemEtInteritum

Page

Toolbox

Search

Difference between revisions of "2020 USOJMO Problems/Problem 5"

Revision as of 12:34, 7 July 2020

Problem

Solution