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 and also
.
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.