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"

(Created page with "Suppose that <math>(a_1,b_1),</math> <math>(a_2,b_2),</math> <math>\dots,</math> <math>(a_{100},b_{100})</math> are distinct ordered pairs of nonnegative integers. Let <math>N...")
 
m
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
Suppose that <math>(a_1,b_1),</math> <math>(a_2,b_2),</math> <math>\dots,</math> <math>(a_{100},b_{100})</math> are distinct ordered pairs of nonnegative integers. Let <math>N</math> denote the number of pairs of integers <math>(i,j)</math> satisfying <math>1\leq i<j\leq 100</math> and <math>|a_ib_j-a_jb_i|=1</math>. Determine the largest possible value of <math>N</math> over all possible choices of the <math>100</math> ordered pairs.
 
Suppose that <math>(a_1,b_1),</math> <math>(a_2,b_2),</math> <math>\dots,</math> <math>(a_{100},b_{100})</math> are distinct ordered pairs of nonnegative integers. Let <math>N</math> denote the number of pairs of integers <math>(i,j)</math> satisfying <math>1\leq i<j\leq 100</math> and <math>|a_ib_j-a_jb_i|=1</math>. Determine the largest possible value of <math>N</math> over all possible choices of the <math>100</math> ordered pairs.
 +
 +
==Solution==
 +
 +
Call the pair <math>(i, j)</math> good if <math>1\leq i < j \leq 100</math> and <math>|a_ib_j-a_jb_i|=1</math>. Note that we can reorder the pairs <math>(a_1, b_1), (a_2, b_2), \ldots, (a_{100}, b_{100})</math> without changing the number of good pairs. Thus, we can reorder them so that <math>a_1\leq a_2\leq\ldots\leq a_{100}</math>. Furthermore, reorder them so that if <math>a_i=a_j</math> for some <math>i<j</math>, then <math>b_i<b_j</math>.
 +
 +
Now I claim the maximum value of <math>N</math> is <math>\boxed{197}</math>. First, we will show <math>N\leq 197</math>.
 +
 +
The key claim is that for any fixed integer <math>m</math>, <math>1\leq m \leq 100</math>, then there are at most 2 values of <math>i</math> with <math>1\leq i<m</math> with the pair <math>(i, m)</math> good. We will prove this with contradiction.
 +
 +
Assume there are 3 integers <math>i</math>, <math>j</math>, and <math>k</math> that are less than <math>m</math>, such that <math>(i, m)</math>, <math>(j, m)</math>, and <math>(k, m)</math> are all good. Note that <math>gcd(a_m, b_m)</math> divides <math>a_ib_m-a_mb_i=\pm 1</math>, so <math>gcd(a_m, b_m)=1</math>. From <math>a_ib_m-a_mb_i=\pm 1</math>, we have <cmath>a_ib_m\equiv \pm 1 \mod a_m</cmath>
 +
Similarly, <cmath>a_jb_m\equiv \pm 1 \mod a_m</cmath> <cmath>a_kb_m\equiv \pm 1 \mod a_m</cmath>
 +
 +
From <math>gcd(a_m, b_m)=1</math> we have <cmath>a_i\equiv \pm a_j \equiv \pm a_k \mod a_m</cmath>
 +
 +
But since <math>i</math>, <math>j</math>, and <math>k</math> are less than <math>m</math>, from our reordering we have <math>0\leq a_i<a_m</math>, <math>0\leq a_j<a_m</math>, and <math>0\leq a_k<a_m</math>. Thus our congruence gives us that <math>a_j=a_i</math> or <math>a_j=a_m-a_i</math>, and similar for <math>a_k</math>. Thus at least two of <math>a_i, a_j, a_k</math> are equal. WLOG let them be <math>a_i</math> and <math>a_j</math>. Now we have 4 cases.
 +
 +
<b>Case 1: <math>a_m>2</math></b>
 +
 +
We have <math>a_ib_m-a_mb_i=\pm 1</math> and <math>a_jb_m-a_mb_j=\pm 1</math>, so since <math>a_i=a_j</math> we can subtract the two equations to get <math>a_mb_i-a_mb_j</math> equals <math>\pm 2, 0</math>. But <math>a_m>2</math>, so <math>|a_m(b_i-b_j)|\leq 2</math> implies that <math>b_i=b_j</math>. But all pairs are distinct and <math>a_i=a_j</math>, so this is a contradiction.
 +
 +
<b>Case 2: <math>a_m=2</math></b>
 +
 +
We have 2 subcases.
 +
 +
<b>Subcase 2a: <math>a_i\equiv a_j\equiv a_k\equiv 1 \mod a_m</math></b>
 +
 +
Clearly we must have <math>a_i=a_j=a_k=1</math> in this case, as all 3 variables are less than <math>a_m=2</math>. Then <math>1\cdot b_m-a_mb_i=\pm 1</math>, <math>1\cdot b_m-a_mb_j=\pm 1</math>, and <math>1\cdot b_m-a_mb_k=\pm 1</math>. So at least 2 of <math>b_i</math>, <math>b_j</math>, and <math>b_k</math> must be equal, but this contradicts the fact that all pairs <math>(a_x, b_x)</math> are distinct.
 +
 +
<b>Subcase 2b: <math>a_i\equiv a_j\equiv a_k\equiv 0 \mod a_m</math></b>
 +
 +
<math>a_i</math> must be even in this case, but since <math>a_m</math> is also even then <math>a_ib_m-a_mb_i</math> must be even, which contradicts <math>|a_ib_m-a_mb_i|=1</math>.
 +
 +
<b>Case 3: <math>a_m=1</math></b>
 +
 +
We must have <math>a_i=0,1</math>, and similarly for <math>a_j</math> and <math>a_k</math>. Thus at least 2 of the 3 must be equal. Now we have 2 subcases again.
 +
 +
<b>Subcase 3a: 2 of the 3 are equal to 0</b>
 +
 +
WLOG let <math>a_i=a_j=0</math>. Then <math>a_ib_m-a_mb_i=\pm 1</math> and <math>a_m=1</math> so <math>b_i=\pm 1</math>. Since <math>b_i</math> is nonnegative, <math>b_i=1</math>. Similarly <math>b_j=1</math>, but all pairs are distinct so we have a contradiction.
 +
 +
<b>Subcase 3b: 2 of the 3 are equal to 1</b>
 +
 +
WLOG let <math>a_i=a_j=0</math>. Then <math>a_ib_m-a_mb_i=\pm 1</math>, so <math>b_m-b_i=\pm 1</math>. But <math>i<m</math> and <math>a_i=a_m=1</math>, so by our ordering of the pairs we have <math>b_i<b_m</math> so <math>b_m-b_i=1</math>. But similarly <math>b_m-b_j=1</math>, so <math>b_i=b_j</math>, which is a contradiction to all pairs being distinct.
 +
 +
<b>Case 4: <math>a_m=0</math></b>
 +
 +
We must have <math>a_i=0</math>, since <math>0\leq a_i\leq a_m=0</math>. Thus <math>a_ib_m-a_mb_i=0</math>, but <math>|a_ib_m-a_mb_i|=1</math>, contradiction.<math>\blacksquare</math>
 +
 +
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),\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
 +
 +
==Solution 2==
 +
We claim the answer is <math>2n-3</math> (so <math>197</math>), where <math>100</math> is to be replaced with <math>n</math>.
 +
 +
The problem essentially counts unordered pairs <math>(P,Q)</math> of lattice points so that <math>POQ</math> has area <math>\frac{1}{2}</math> due to Shoelace (<math>O</math> is the origin).
 +
 +
For a construction, take the points <math>(0,1),(1,1),(1,2), \dots (1,n-1)</math>.
 +
 +
We now show by induction that <math>2n-3</math> is the maximum, where <math>n=2</math> obviously holds as a base case.
 +
 +
To reduce to the inductive hypothesis of <math>n-1</math> points from <math>n</math> points, we are allowed to consider the point with the greatest sum of coordinates <math>R</math>.
 +
 +
The key claim is that <math>R</math> is part of at most <math>2</math> pairs (triangles) with area <math>\frac{1}{2}</math>.
 +
 +
Before we proceed, note that <math>R</math> must have relatively prime coordinates <math>(m,n)</math>, or else any triangles found can be reduced down by a greatest common factor along <math>OR</math>, impossible since <math>\frac{1}{2}</math> is the minimum positive area.
 +
 +
Call the hypothetical point(s) <math>X</math>. With triangle <math>XOR</math> with area <math>\frac{1}{2}</math>, we know the length of <math>OR</math>, so indeed the locus of <math>X</math> is two lines evenly spaced next to <math>OR</math> each parallel to <math>OR</math> (before we consider the lattice condition).
 +
 +
When we add in the lattice condition, we see that each of these two lines contain at most one valid <math>X</math>. This is because if two lattice points with non-negative integers lied on one of these lines, one would have to be a multiple of <math>m</math> more than the other on the <math>x</math>-coordinates and a multiple of <math>n</math> more on the <math>y</math>-coordinates. This contradicts the coordinate sum maximality of <math>R</math>.
 +
 +
Thus, by deleting <math>R</math>, we lose at most two pairs <math>(X,R)</math>, completing the induction and the problem.
 +
 +
==See Also==
 +
{{USAJMO newbox|year=2020|num-b=4|num-a=6}}
 +
{{MAA Notice}}

Latest revision as of 18:16, 6 October 2023

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

Solution 2

We claim the answer is $2n-3$ (so $197$), where $100$ is to be replaced with $n$.

The problem essentially counts unordered pairs $(P,Q)$ of lattice points so that $POQ$ has area $\frac{1}{2}$ due to Shoelace ($O$ is the origin).

For a construction, take the points $(0,1),(1,1),(1,2), \dots (1,n-1)$.

We now show by induction that $2n-3$ is the maximum, where $n=2$ obviously holds as a base case.

To reduce to the inductive hypothesis of $n-1$ points from $n$ points, we are allowed to consider the point with the greatest sum of coordinates $R$.

The key claim is that $R$ is part of at most $2$ pairs (triangles) with area $\frac{1}{2}$.

Before we proceed, note that $R$ must have relatively prime coordinates $(m,n)$, or else any triangles found can be reduced down by a greatest common factor along $OR$, impossible since $\frac{1}{2}$ is the minimum positive area.

Call the hypothetical point(s) $X$. With triangle $XOR$ with area $\frac{1}{2}$, we know the length of $OR$, so indeed the locus of $X$ is two lines evenly spaced next to $OR$ each parallel to $OR$ (before we consider the lattice condition).

When we add in the lattice condition, we see that each of these two lines contain at most one valid $X$. This is because if two lattice points with non-negative integers lied on one of these lines, one would have to be a multiple of $m$ more than the other on the $x$-coordinates and a multiple of $n$ more on the $y$-coordinates. This contradicts the coordinate sum maximality of $R$.

Thus, by deleting $R$, we lose at most two pairs $(X,R)$, completing the induction and the problem.

See Also

2020 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=2020_USOJMO_Problems/Problem_5&oldid=199255"