Difference between revisions of "2020 USOJMO Problems/Problem 5"
(Created page with "Suppose that <math>(a_1,b_1),</math> <math>(a_2,b_2),</math> <math>\dots,</math> <math>(a_{100},b_{100})</math> are distinct ordered pairs of nonnegative integers. Let <math>N...") |
m |
||
(6 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
+ | ==Problem== | ||
+ | |||
Suppose that <math>(a_1,b_1),</math> <math>(a_2,b_2),</math> <math>\dots,</math> <math>(a_{100},b_{100})</math> are distinct ordered pairs of nonnegative integers. Let <math>N</math> denote the number of pairs of integers <math>(i,j)</math> satisfying <math>1\leq i<j\leq 100</math> and <math>|a_ib_j-a_jb_i|=1</math>. Determine the largest possible value of <math>N</math> over all possible choices of the <math>100</math> ordered pairs. | Suppose that <math>(a_1,b_1),</math> <math>(a_2,b_2),</math> <math>\dots,</math> <math>(a_{100},b_{100})</math> are distinct ordered pairs of nonnegative integers. Let <math>N</math> denote the number of pairs of integers <math>(i,j)</math> satisfying <math>1\leq i<j\leq 100</math> and <math>|a_ib_j-a_jb_i|=1</math>. Determine the largest possible value of <math>N</math> over all possible choices of the <math>100</math> ordered pairs. | ||
+ | |||
+ | ==Solution== | ||
+ | |||
+ | Call the pair <math>(i, j)</math> good if <math>1\leq i < j \leq 100</math> and <math>|a_ib_j-a_jb_i|=1</math>. Note that we can reorder the pairs <math>(a_1, b_1), (a_2, b_2), \ldots, (a_{100}, b_{100})</math> without changing the number of good pairs. Thus, we can reorder them so that <math>a_1\leq a_2\leq\ldots\leq a_{100}</math>. Furthermore, reorder them so that if <math>a_i=a_j</math> for some <math>i<j</math>, then <math>b_i<b_j</math>. | ||
+ | |||
+ | Now I claim the maximum value of <math>N</math> is <math>\boxed{197}</math>. First, we will show <math>N\leq 197</math>. | ||
+ | |||
+ | The key claim is that for any fixed integer <math>m</math>, <math>1\leq m \leq 100</math>, then there are at most 2 values of <math>i</math> with <math>1\leq i<m</math> with the pair <math>(i, m)</math> good. We will prove this with contradiction. | ||
+ | |||
+ | Assume there are 3 integers <math>i</math>, <math>j</math>, and <math>k</math> that are less than <math>m</math>, such that <math>(i, m)</math>, <math>(j, m)</math>, and <math>(k, m)</math> are all good. Note that <math>gcd(a_m, b_m)</math> divides <math>a_ib_m-a_mb_i=\pm 1</math>, so <math>gcd(a_m, b_m)=1</math>. From <math>a_ib_m-a_mb_i=\pm 1</math>, we have <cmath>a_ib_m\equiv \pm 1 \mod a_m</cmath> | ||
+ | Similarly, <cmath>a_jb_m\equiv \pm 1 \mod a_m</cmath> <cmath>a_kb_m\equiv \pm 1 \mod a_m</cmath> | ||
+ | |||
+ | From <math>gcd(a_m, b_m)=1</math> we have <cmath>a_i\equiv \pm a_j \equiv \pm a_k \mod a_m</cmath> | ||
+ | |||
+ | But since <math>i</math>, <math>j</math>, and <math>k</math> are less than <math>m</math>, from our reordering we have <math>0\leq a_i<a_m</math>, <math>0\leq a_j<a_m</math>, and <math>0\leq a_k<a_m</math>. Thus our congruence gives us that <math>a_j=a_i</math> or <math>a_j=a_m-a_i</math>, and similar for <math>a_k</math>. Thus at least two of <math>a_i, a_j, a_k</math> are equal. WLOG let them be <math>a_i</math> and <math>a_j</math>. Now we have 4 cases. | ||
+ | |||
+ | <b>Case 1: <math>a_m>2</math></b> | ||
+ | |||
+ | We have <math>a_ib_m-a_mb_i=\pm 1</math> and <math>a_jb_m-a_mb_j=\pm 1</math>, so since <math>a_i=a_j</math> we can subtract the two equations to get <math>a_mb_i-a_mb_j</math> equals <math>\pm 2, 0</math>. But <math>a_m>2</math>, so <math>|a_m(b_i-b_j)|\leq 2</math> implies that <math>b_i=b_j</math>. But all pairs are distinct and <math>a_i=a_j</math>, so this is a contradiction. | ||
+ | |||
+ | <b>Case 2: <math>a_m=2</math></b> | ||
+ | |||
+ | We have 2 subcases. | ||
+ | |||
+ | <b>Subcase 2a: <math>a_i\equiv a_j\equiv a_k\equiv 1 \mod a_m</math></b> | ||
+ | |||
+ | Clearly we must have <math>a_i=a_j=a_k=1</math> in this case, as all 3 variables are less than <math>a_m=2</math>. Then <math>1\cdot b_m-a_mb_i=\pm 1</math>, <math>1\cdot b_m-a_mb_j=\pm 1</math>, and <math>1\cdot b_m-a_mb_k=\pm 1</math>. So at least 2 of <math>b_i</math>, <math>b_j</math>, and <math>b_k</math> must be equal, but this contradicts the fact that all pairs <math>(a_x, b_x)</math> are distinct. | ||
+ | |||
+ | <b>Subcase 2b: <math>a_i\equiv a_j\equiv a_k\equiv 0 \mod a_m</math></b> | ||
+ | |||
+ | <math>a_i</math> must be even in this case, but since <math>a_m</math> is also even then <math>a_ib_m-a_mb_i</math> must be even, which contradicts <math>|a_ib_m-a_mb_i|=1</math>. | ||
+ | |||
+ | <b>Case 3: <math>a_m=1</math></b> | ||
+ | |||
+ | We must have <math>a_i=0,1</math>, and similarly for <math>a_j</math> and <math>a_k</math>. Thus at least 2 of the 3 must be equal. Now we have 2 subcases again. | ||
+ | |||
+ | <b>Subcase 3a: 2 of the 3 are equal to 0</b> | ||
+ | |||
+ | WLOG let <math>a_i=a_j=0</math>. Then <math>a_ib_m-a_mb_i=\pm 1</math> and <math>a_m=1</math> so <math>b_i=\pm 1</math>. Since <math>b_i</math> is nonnegative, <math>b_i=1</math>. Similarly <math>b_j=1</math>, but all pairs are distinct so we have a contradiction. | ||
+ | |||
+ | <b>Subcase 3b: 2 of the 3 are equal to 1</b> | ||
+ | |||
+ | WLOG let <math>a_i=a_j=0</math>. Then <math>a_ib_m-a_mb_i=\pm 1</math>, so <math>b_m-b_i=\pm 1</math>. But <math>i<m</math> and <math>a_i=a_m=1</math>, so by our ordering of the pairs we have <math>b_i<b_m</math> so <math>b_m-b_i=1</math>. But similarly <math>b_m-b_j=1</math>, so <math>b_i=b_j</math>, which is a contradiction to all pairs being distinct. | ||
+ | |||
+ | <b>Case 4: <math>a_m=0</math></b> | ||
+ | |||
+ | We must have <math>a_i=0</math>, since <math>0\leq a_i\leq a_m=0</math>. Thus <math>a_ib_m-a_mb_i=0</math>, but <math>|a_ib_m-a_mb_i|=1</math>, contradiction.<math>\blacksquare</math> | ||
+ | |||
+ | 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),\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 | ||
+ | |||
+ | ==Solution 2== | ||
+ | We claim the answer is <math>2n-3</math> (so <math>197</math>), where <math>100</math> is to be replaced with <math>n</math>. | ||
+ | |||
+ | The problem essentially counts unordered pairs <math>(P,Q)</math> of lattice points so that <math>POQ</math> has area <math>\frac{1}{2}</math> due to Shoelace (<math>O</math> is the origin). | ||
+ | |||
+ | For a construction, take the points <math>(0,1),(1,1),(1,2), \dots (1,n-1)</math>. | ||
+ | |||
+ | We now show by induction that <math>2n-3</math> is the maximum, where <math>n=2</math> obviously holds as a base case. | ||
+ | |||
+ | To reduce to the inductive hypothesis of <math>n-1</math> points from <math>n</math> points, we are allowed to consider the point with the greatest sum of coordinates <math>R</math>. | ||
+ | |||
+ | The key claim is that <math>R</math> is part of at most <math>2</math> pairs (triangles) with area <math>\frac{1}{2}</math>. | ||
+ | |||
+ | 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> 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>. | ||
+ | |||
+ | Thus, by deleting <math>R</math>, we lose at most two pairs <math>(X,R)</math>, completing the induction and the problem. | ||
+ | |||
+ | ==See Also== | ||
+ | {{USAJMO newbox|year=2020|num-b=4|num-a=6}} | ||
+ | {{MAA Notice}} |
Latest revision as of 19:16, 6 October 2023
Contents
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.
See Also
2020 USAJMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.