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

Revision as of 22:21, 10 April 2021

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

@@ Line 55: / Line 55: @@
 ~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>, 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.

Page

Toolbox

Search

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

Revision as of 22:21, 10 April 2021

Problem

Solution

Solution 2