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 USAMO Problems/Problem 4"

(→‎Solution)
 
(6 intermediate revisions by one other user not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
Let's start off with just <math>(a_1, b_1), (a_2, b_2)</math> and suppose that it satisfies the given condition. We could use <math>(1, 1), (1, 2)</math> for example. We should maximize the number of conditions that the third pair satisfies. We find out that the third pair should equal <math>(a_1+a_2, b_1+b_2)</math> or <math>(|a_1-a_2|, |b_1-b_2|)</math>
+
Let's start off with just <math>(a_1, b_1), (a_2, b_2)</math> and suppose that it satisfies the given condition. We could use <math>(1, 1), (1, 2)</math> for example. We should maximize the number of conditions that the third pair satisfies. We find out that the third pair should equal <math>(a_1+a_2, b_1+b_2)</math>:
  
 
We know this must be true:
 
We know this must be true:
Line 32: Line 32:
 
<cmath>a_4 = a_1+2a_2</cmath>
 
<cmath>a_4 = a_1+2a_2</cmath>
 
<cmath>b_4 = b_1+2b_2</cmath>
 
<cmath>b_4 = b_1+2b_2</cmath>
−
<cmath>a_1b_1+2a_2b_1-a_1b_1-2a_1b_2 = \pm1</cmath>
+
<cmath>|a_1b_1+2a_2b_1-a_1b_1-2a_1b_2| = 1</cmath>
−
<cmath>2(a_2b_1-a_1b_2) = \pm1</cmath>
+
<cmath>2|a_2b_1-a_1b_2| = 1</cmath>
  
−
This is clearly impossible because RHS must be even.
+
This is clearly impossible because <math>1</math> is not even and also <math>|a_2b_1-a_1b_2| = 1</math>.
−
OK, so we done. Not yet. We not solve answer yet. The answer is clearly that:
+
The answer is as follows:
 
<cmath>0+1+2+\ldots+2</cmath>
 
<cmath>0+1+2+\ldots+2</cmath>
 
<math>a_1</math> has <math>0</math> subtractions that follow condition while <math>a_2</math> has <math>1</math> and then the rest has <math>2</math>.
 
<math>a_1</math> has <math>0</math> subtractions that follow condition while <math>a_2</math> has <math>1</math> and then the rest has <math>2</math>.
 
There are <math>n</math> terms, so our answer be <math>2n-3</math> and in case of <math>n=100</math> that means  
 
There are <math>n</math> terms, so our answer be <math>2n-3</math> and in case of <math>n=100</math> that means  
 
<cmath>\boxed{N=197}.</cmath>~Lopkiloinm
 
<cmath>\boxed{N=197}.</cmath>~Lopkiloinm
 +
 +
==Solution 2==
 +
We claim the answer is <math>197</math>.
 +
 +
Study the points <math>(0, 0), (a_i, b_i), (a_j, b_j)</math>. If we let these be the vertices of a triangle, applying shoelace theorem gives us an area of <math>\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}</math>. Therefore, the triangle formed by the points <math>(0, 0), (a_i, b_i), (a_j, b_j)</math> must have an area of <math>\frac{1}{2}</math>.
 +
 +
Two cases follow.
 +
Case 1: Both <math>(a_i, b_i), (a_j, b_j)</math> have exactly one coordinate equal to <math>0</math>.
 +
Here, one point must be on the <math>x</math> axis and the other on the <math>y</math> axis in order for the triangle to have a positive area. For the area of the triangle to be <math>\frac{1}{2}</math>, it follows that the points must be <math>(1, 0), (0, 1)</math> in some order.
 +
 +
Case 2: At least one of <math>(a_i, b_i), (a_j, b_j)</math> does not have exactly one coordinate equal to <math>0</math>. Define <math>S[l]</math> to be a list of lines such that each line in the list has some two lattice points that, with <math>(0, 0)</math>, form a triangle with area <math>\frac{1}{2}</math>. 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 <math>y=1</math> and <math>x=1</math> are included in <math>S[l]</math>, because the points <math>(1, 1), (2, 1)</math> serve as examples for <math>y=1</math> and <math>(1, 1), (1, 2)</math> serve as examples for <math>x=1</math>. For the optimal construction, include the points <math>(1, 0)</math> and all the points <math>(0, 1), (0, 2), (0, 3), ... , (0, 99)</math>, in that order. In this case, every adjacent pair of points would count (<math>98</math>), as well as picking <math>(0, 1)</math> and a nonadjacent point (<math>99</math>), so this would be <math>98+99=197</math>.
 +
 +
To prove that this is the maximum, consider the case where some <math>n</math> number of points were neither on <math>x=1</math> nor on <math>y=1</math>. In this case, we would be removing <math>n</math> adjacent pairs and <math>n</math> options to choose from after choosing <math>(0, 0)</math>, resulting in a net loss of <math>2n</math>. By having <math>n</math> points on some other combination of lines in <math>S[l]</math>, we would trivially have a maximum gain of <math>n-1</math> pairs of points on the lines such that there are no lattice points between those pairs. Because these points are not on <math>x=1</math> or <math>y=1</math>, the altitude from a given point to the line formed by <math>(0, 0)</math> and <math>(0, 1)</math> and <math>(1, 0)</math> is not <math>1</math>, and so the area of the triangle cannot be <math>\frac{1}{2}</math>. Thus, by not having all points on lines <math>x=1</math> and <math>y=1</math>, we cannot exceed the maximum of <math>197</math>. Thus, <math>\boxed{197}</math> is our answer.
 +
 +
~SigmaPiE
 +
 +
  
 
==See also==
 
==See also==
 
{{USAMO newbox|year=2020|num-b=3|num-a=5}}
 
{{USAMO newbox|year=2020|num-b=3|num-a=5}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 11:40, 18 June 2023

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


See also

2020 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO 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_USAMO_Problems/Problem_4&oldid=194589"