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 "2020 USOJMO Problems/Problem 5"
(→‎Solution)
Line 53: Line 53:
  
 
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)...(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

Revision as of 12:33, 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)...(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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_USOJMO_Problems/Problem_5&oldid=127676"