Difference between revisions of "2020 USOJMO Problems/Problem 5"
(→Solution) |
(→Solution) |
||
Line 52: | Line 52: | ||
Thus our claim is proved. Now for <math>m=1</math>, there is clearly no <math>i</math> with <math>1\leq i < m \leq 100</math> and <math>(i, m)</math> good. For <math>m=2</math>, there is at most one value of i with <math>1\leq i < m \leq 100</math> and <math>(i, m)</math> good (namely, this is when <math>i=1</math>). By our claim, for all <math>2<m\leq 100</math> there are at most 2 values of <math>i</math> with <math>1\leq i < m \leq 100</math> and <math>(i, m)</math> good, so adding these up gives at most <math>2\cdot 98+1=197</math> good pairs. Now we will show that 197 good pairs is achievable. | Thus our claim is proved. Now for <math>m=1</math>, there is clearly no <math>i</math> with <math>1\leq i < m \leq 100</math> and <math>(i, m)</math> good. For <math>m=2</math>, there is at most one value of i with <math>1\leq i < m \leq 100</math> and <math>(i, m)</math> good (namely, this is when <math>i=1</math>). By our claim, for all <math>2<m\leq 100</math> there are at most 2 values of <math>i</math> with <math>1\leq i < m \leq 100</math> and <math>(i, m)</math> good, so adding these up gives at most <math>2\cdot 98+1=197</math> good pairs. Now we will show that 197 good pairs is achievable. | ||
− | The sequence <math>(1,1) (1,2) (2,3) | + | The sequence <math>(1,1), (1,2), (2,3),\ldots ,(99,100)</math> has 197 good pairs - namely, <math>(1, n)</math> is good for all <math>1<n\leq 100</math>, and <math>(i, i+1)</math> is good for all <math>1<i<100</math>. This adds up for a total of 197 good pairs, so we are done. <math>\blacksquare</math> |
~MortemEtInteritum | ~MortemEtInteritum |
Revision as of 13:34, 7 July 2020
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