# Difference between revisions of "2020 USOJMO Problems/Problem 5"

(→Solution) |
(→Solution) |
||

Line 55: | Line 55: | ||

~MortemEtInteritum | ~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>, 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. |

## Revision as of 23:21, 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 , 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.