2020 USAMO Problems/Problem 4
Contents
[hide]Problem 4
Suppose that are distinct ordered pairs of nonnegative integers. Let denote the number of pairs of integers satisfying and . Determine the largest possible value of over all possible choices of the ordered pairs.
Solution
Let's start off with just and suppose that it satisfies the given condition. We could use for example. We should maximize the number of conditions that the third pair satisfies. We find out that the third pair should equal :
We know this must be true:
So
We require the maximum conditions for
Then one case can be:
We try to do some stuff such as solving for with manipulations:
We showed that 3 pairs are a complete graph; however, 4 pairs are not a complete graph. We will now show that:
This is clearly impossible because is not even and also . The answer is as follows: has subtractions that follow condition while has and then the rest has . There are terms, so our answer be and in case of that means ~Lopkiloinm
Solution 2
We claim the answer is .
Study the points . If we let these be the vertices of a triangle, applying shoelace theorem gives us an area of . Therefore, the triangle formed by the points must have an area of .
Two cases follow. Case 1: Both have exactly one coordinate equal to . Here, one point must be on the axis and the other on the axis in order for the triangle to have a positive area. For the area of the triangle to be , it follows that the points must be in some order.
Case 2: At least one of does not have exactly one coordinate equal to . Define to be a list of lines such that each line in the list has some two lattice points that, with , form a triangle with area . 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 and are included in , because the points serve as examples for and serve as examples for . For the optimal construction, include the points and all the points , in that order. In this case, every adjacent pair of points would count (), as well as picking and a nonadjacent point (), so this would be .
To prove that this is the maximum, consider the case where some number of points were neither on nor on . In this case, we would be removing adjacent pairs and options to choose from after choosing , resulting in a net loss of . By having points on some other combination of lines in , we would trivially have a maximum gain of pairs of points on the lines such that there are no lattice points between those pairs. Because these points are not on or , the altitude from a given point to the line formed by and and is not , and so the area of the triangle cannot be . Thus, by not having all points on lines and , we cannot exceed the maximum of . Thus, 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.