During AMC testing, the AoPS Wiki is in read-only mode. No edits can be made.

# 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
The text passage contains a mathematical problem and its solution, including a specific question and the answer to that question.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
During AMC testing, the AoPS Wiki is in read-only mode. No edits can be made.

# 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
user
The text passage contains a mathematical problem and its solution, including a specific question and the answer to that question.

TYPE: SINGLE_QUESTION_WITH_ANSWER