Difference between revisions of "2020 USOJMO Problems/Problem 5"
(→Solution) |
m (→Solution 2) |
||
Line 71: | Line 71: | ||
Before we proceed, note that <math>R</math> must have relatively prime coordinates <math>(m,n)</math>, or else any triangles found can be reduced down by a greatest common factor along <math>OR</math>, impossible since <math>\frac{1}{2}</math> is the minimum positive area. | Before we proceed, note that <math>R</math> must have relatively prime coordinates <math>(m,n)</math>, or else any triangles found can be reduced down by a greatest common factor along <math>OR</math>, impossible since <math>\frac{1}{2}</math> is the minimum positive area. | ||
− | Call the hypothetical point(s) <math>X</math>. With triangle <math>XOR</math>, we know the length of <math>OR</math>, so indeed the locus of <math>X</math> is two lines evenly spaced next to <math>OR</math> each parallel to <math>OR</math> (before we consider the lattice condition). | + | Call the hypothetical point(s) <math>X</math>. With triangle <math>XOR</math> with area <math>\frac{1}{2}</math>, we know the length of <math>OR</math>, so indeed the locus of <math>X</math> is two lines evenly spaced next to <math>OR</math> each parallel to <math>OR</math> (before we consider the lattice condition). |
When we add in the lattice condition, we see that each of these two lines contain at most one valid <math>X</math>. This is because if two lattice points with non-negative integers lied on one of these lines, one would have to be a multiple of <math>m</math> more than the other on the <math>x</math>-coordinates and a multiple of <math>n</math> more on the <math>y</math>-coordinates. This contradicts the coordinate sum maximality of <math>R</math>. | When we add in the lattice condition, we see that each of these two lines contain at most one valid <math>X</math>. This is because if two lattice points with non-negative integers lied on one of these lines, one would have to be a multiple of <math>m</math> more than the other on the <math>x</math>-coordinates and a multiple of <math>n</math> more on the <math>y</math>-coordinates. This contradicts the coordinate sum maximality of <math>R</math>. | ||
Thus, by deleting <math>R</math>, we lose at most two pairs <math>(X,R)</math>, completing the induction and the problem. | Thus, by deleting <math>R</math>, we lose at most two pairs <math>(X,R)</math>, completing the induction and the problem. |
Revision as of 23:22, 10 April 2021
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
Solution 2
We claim the answer is (so
), where
is to be replaced with
.
The problem essentially counts unordered pairs of lattice points so that
has area
due to Shoelace (
is the origin).
For a construction, take the points .
We now show by induction that is the maximum, where
obviously holds as a base case.
To reduce to the inductive hypothesis of points from
points, we are allowed to consider the point with the greatest sum of coordinates
.
The key claim is that is part of at most
pairs (triangles) with area
.
Before we proceed, note that must have relatively prime coordinates
, or else any triangles found can be reduced down by a greatest common factor along
, impossible since
is the minimum positive area.
Call the hypothetical point(s) . With triangle
with area
, we know the length of
, so indeed the locus of
is two lines evenly spaced next to
each parallel to
(before we consider the lattice condition).
When we add in the lattice condition, we see that each of these two lines contain at most one valid . This is because if two lattice points with non-negative integers lied on one of these lines, one would have to be a multiple of
more than the other on the
-coordinates and a multiple of
more on the
-coordinates. This contradicts the coordinate sum maximality of
.
Thus, by deleting , we lose at most two pairs
, completing the induction and the problem.