2020 USOJMO Problems/Problem 5
Problem
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
Call the pair good if
and
. Note that we can reorder the pairs
without changing the number of good pairs. Thus, we can reorder them so that
. Furthermore, reorder them so that if
for some
, then
.
Now I claim the maximum value of is
. First, we will show
.
The key claim is that for any fixed integer ,
, then there are at most 2 values of
with
with the pair
good. We will prove this with contradiction.
Assume there are 3 integers ,
, and
that are less than
, such that
,
, and
are all good. Note that
divides
, so
. From
, we have
Similarly,
From we have
But since ,
, and
are less than
, from our reordering we have
,
, and
. Thus our congruence gives us that
or
, and similar for
. Thus at least two of
are equal. WLOG let them be
and
. Now we have 4 cases.
Case 1:
We have and
, so since
we can subtract the two equations to get
equals
. But
, so
implies that
. But all pairs are distinct and
, so this is a contradiction.
Case 2:
We have 2 subcases.
Subcase 2a:
Clearly we must have in this case, as all 3 variables are less than
. Then
,
, and
. So at least 2 of
,
, and
must be equal, but this contradicts the fact that all pairs
are distinct.
Subcase 2b:
must be even in this case, but since
is also even then
must be even, which contradicts
.
Case 3:
We must have , and similarly for
and
. Thus at least 2 of the 3 must be equal. Now we have 2 subcases again.
Subcase 3a: 2 of the 3 are equal to 0
WLOG let . Then
and
so
. Since
is nonnegative,
. Similarly
, but all pairs are distinct so we have a contradiction.
Subcase 3b: 2 of the 3 are equal to 1
WLOG let . Then
, so
. But
and
, so by our ordering of the pairs we have
so
. But similarly
, so
, which is a contradiction to all pairs being distinct.
Case 4:
We must have , since
. Thus
, but
, contradiction.
Thus our claim is proved. Now for , there is clearly no
with
and
good. For
, there is at most one value of i with
and
good (namely, this is when
). By our claim, for all
there are at most 2 values of
with
and
good, so adding these up gives at most
good pairs. Now we will show that 197 good pairs is achievable.
The sequence has 197 good pairs - namely,
is good for all
, and
is good for all
. This adds up for a total of 197 good pairs, so we are done.
~MortemEtInteritum