2020 USAMO Problems/Problem 4
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. The answer is clearly: 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
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.