2020 USAMO Problems/Problem 4

Problem 4

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

Solution

Let's start off with just $(a_1, b_1), (a_2, b_2)$ and suppose that it satisfies the given condition. We could use $(1, 1), (1, 2)$ for example. We should maximize the number of conditions that the third pair satisfies. We find out that the third pair should equal $(a_1+a_2, b_1+b_2)$ :

We know this must be true: $|a_1b_2-a_2b_1| = 1$

So $a_1b_2-a_2b_1 = 1$

We require the maximum conditions for $(a_3, b_3)$ $|a_3b_2-a_2b_3| = 1$ $|a_3b_1-a_1b_3| = 1$

Then one case can be: $a_3b_2-a_2b_3 = 1$ $a_3b_1-a_1b_3 = -1$

We try to do some stuff such as solving for $a_3$ with manipulations: $a_3b_2a_1-a_2b_3a_1 = a_1$ $a_3b_1a_2-a_1b_3a_2 = -a_2$ $a_3(a_1b_2-a_2b_1) = a_1+a_2$ $a_3 = a_1+a_2$ $a_3b_2b_1-a_2b_3b_1 = b_1$ $a_3b_1b_2-a_1b_3b_2 = -b_2$ $b_3(a_1b_2-a_2b_1) = b_1+b_2$ $b_3 = b_1+b_2$

We showed that 3 pairs are a complete graph; however, 4 pairs are not a complete graph. We will now show that: $a_4 = a_1+2a_2$ $b_4 = b_1+2b_2$ $|a_1b_1+2a_2b_1-a_1b_1-2a_1b_2| = 1$ $2|a_2b_1-a_1b_2| = 1$

This is clearly impossible because $1$ is not even and also $|a_2b_1-a_1b_2| = 1$ . The answer is as follows: $0+1+2+\ldots+2$ $a_1$ has $0$ subtractions that follow condition while $a_2$ has $1$ and then the rest has $2$ . There are $n$ terms, so our answer be $2n-3$ and in case of $n=100$ that means $\boxed{N=197}.$ ~Lopkiloinm

Solution 2

We claim the answer is $197$ .

Study the points $(0, 0), (a_i, b_i), (a_j, b_j)$ . If we let these be the vertices of a triangle, applying shoelace theorem gives us an area of $\frac{1}{2}|0\times{b_i}+{a_i}\times{b_j}+{b_i}\times{0}-0\times{a_i}-{b_i}\times{a_j}-{b_j}\times{0} = \frac{1}{2}|a_ib_j - a_j b_i| = \frac{1}{2}$ . Therefore, the triangle formed by the points $(0, 0), (a_i, b_i), (a_j, b_j)$ must have an area of $\frac{1}{2}$ .

Two cases follow. Case 1: Both $(a_i, b_i), (a_j, b_j)$ have exactly one coordinate equal to $0$ . Here, one point must be on the $x$ axis and the other on the $y$ axis in order for the triangle to have a positive area. For the area of the triangle to be $\frac{1}{2}$ , it follows that the points must be $(1, 0), (0, 1)$ in some order.

Case 2: At least one of $(a_i, b_i), (a_j, b_j)$ does not have exactly one coordinate equal to $0$ . Define $S[l]$ to be a list of lines such that each line in the list has some two lattice points that, with $(0, 0)$ , form a triangle with area $\frac{1}{2}$ . Note that for any such line that passes through such two lattice points, we may trivially generate infinite lattice points on the line that have nonnegative coordinates.

Note that lines $y=1$ and $x=1$ are included in $S[l]$ , because the points $(1, 1), (2, 1)$ serve as examples for $y=1$ and $(1, 1), (1, 2)$ serve as examples for $x=1$ . For the optimal construction, include the points $(1, 0)$ and all the points $(0, 1), (0, 2), (0, 3), ... , (0, 99)$ , in that order. In this case, every adjacent pair of points would count ( $98$ ), as well as picking $(0, 1)$ and a nonadjacent point ( $99$ ), so this would be $98+99=197$ .

To prove that this is the maximum, consider the case where some $n$ number of points were neither on $x=1$ nor on $y=1$ . In this case, we would be removing $n$ adjacent pairs and $n$ options to choose from after choosing $(0, 0)$ , resulting in a net loss of $2n$ . By having $n$ points on some other combination of lines in $S[l]$ , we would trivially have a maximum gain of $n-1$ pairs of points on the lines such that there are no lattice points between those pairs. Because these points are not on $x=1$ or $y=1$ , the altitude from a given point to the line formed by $(0, 0)$ and $(0, 1)$ and $(1, 0)$ is not $1$ , and so the area of the triangle cannot be $\frac{1}{2}$ . Thus, by not having all points on lines $x=1$ and $y=1$ , we cannot exceed the maximum of $197$ . Thus, $\boxed{197}$ is our answer.

~SigmaPiE

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

Page

Toolbox

Search

2020 USAMO Problems/Problem 4

Contents

Problem 4

Solution

Solution 2

See also