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