USAMO 2017 Solution Notes

Evan Chen《陳誼廷》
2 June 2023

This is a compilation of solutions for the 2017 USAMO. Some of the

solutions are my own work, but many are from the official solutions provided
by the organizers (for which they hold any copyrights), and others were found
by users on the Art of Problem Solving forums.
These notes will tend to be a bit more advanced and terse than the “official”
solutions from the organizers. In particular, if a theorem or technique is not
known to beginners but is still considered “standard”, then I often prefer to
use this theory anyways, rather than try to work around or conceal it. For
example, in geometry problems I typically use directed angles without further
comment, rather than awkwardly work around configuration issues. Similarly,
sentences like “let R denote the set of real numbers” are typically omitted
entirely.
Corrections and comments are welcome!

Contents
0 Problems 2

1 Solutions to Day 1 3
1.1 USAMO 2017/1, proposed by Gregory Galperin . . . . . . . . . . . . . . . 3
1.2 USAMO 2017/2, proposed by Maria Monks . . . . . . . . . . . . . . . . . 4
1.3 USAMO 2017/3, proposed by Evan Chen . . . . . . . . . . . . . . . . . . 7

2 Solutions to Day 2 9
2.1 USAMO 2017/4, proposed by Maria Monks . . . . . . . . . . . . . . . . . 9
2.2 USAMO 2017/5, proposed by Ricky Liu . . . . . . . . . . . . . . . . . . . 12
2.3 USAMO 2017/6, proposed by Titu Andreescu . . . . . . . . . . . . . . . . 14

1
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

§0 Problems
1. Prove that there exist infinitely many pairs of relatively prime positive integers
a, b > 1 for which a + b divides ab + ba .

2. Let m1 , m2 , . . . , mn be a collection of n positive integers, not necessarily distinct.

For any sequence of integers A = (a1 , . . . , an ) and any permutation w = w1 , . . . , wn
of m1 , . . . , mn , define an A-inversion of w to be a pair of entries wi , wj with i < j
for which one of the following conditions holds:
• ai ≥ wi > wj ,
• wj > ai ≥ wi , or
• wi > w j > a i .
Show that, for any two sequences of integers A = (a1 , . . . , an ) and B = (b1 , . . . , bn ),
and for any positive integer k, the number of permutations of m1 , . . . , mn having
exactly k A-inversions is equal to the number of permutations of m1 , . . . , mn having
exactly k B-inversions.

3. Let ABC be a scalene triangle with circumcircle Ω and incenter I. Ray AI meets
BC at D and Ω again at M ; the circle with diameter DM cuts Ω again at K.
Lines M K and BC meet at S, and N is the midpoint of IS. The circumcircles of
4KID and 4M AN intersect at points L1 and L2 . Prove that Ω passes through
the midpoint of either IL1 or IL2 .

4. Let P1 , P2 , . . . , P2n be 2n distinct points on the unit circle x2 + y 2 = 1, other

than (1, 0). Each point is colored either red or blue, with exactly n red points and
n blue points. Let R1 , R2 , . . . , Rn be any ordering of the red points. Let B1 be
the nearest blue point to R1 traveling counterclockwise around the circle starting
from R1 . Then let B2 be the nearest of the remaining blue points to R2 travelling
counterclockwise around the circle from R2 , and so on, until we have labeled all of
the blue points B1 , . . . , Bn . Show that the number of counterclockwise arcs of the
form Ri → Bi that contain the point (1, 0) is independent of the way we chose the
ordering R1 , . . . , Rn of the red points.

5. Find all real numbers c > 0 such that there exists a labeling of the lattice points in
Z2 with positive integers for which:
• only finitely many distinct labels occur, and
• for each label i, the distance between any two points labeled i is at least ci .

6. Find the minimum possible value of

a b c d
+ 3 + 3 + 3
b3 +4 c +4 d +4 a +4
given that a, b, c, d are nonnegative real numbers such that a + b + c + d = 4.

2
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

§1 Solutions to Day 1
§1.1 USAMO 2017/1, proposed by Gregory Galperin
Available online at https://aops.com/community/p8108366.

Problem statement

Prove that there exist infinitely many pairs of relatively prime positive integers
a, b > 1 for which a + b divides ab + ba .

One construction: let d ≡ 1 (mod 4), d > 1. Let x = d+2 .

dd +2d
Then set

x+d x−d
a= , b= .
2 2
To see this works, first check that b is odd and a is even. Let d = a − b be odd. Then:

a + b | ab + ba ⇐⇒ (−b)b + ba ≡ 0 (mod a + b)
a−b
⇐⇒ b ≡1 (mod a + b)
⇐⇒ bd ≡ 1 (mod d + 2b)
⇐⇒ (−2) ≡ dd d
(mod d + 2b)
⇐⇒ d + 2b | dd + 2d .

So it would be enough that

dd + 2d dd + 2d
 
1
d + 2b = =⇒ b = −d
d+2 2 d+2

which is what we constructed. Also, since gcd(x, d) = 1 it follows gcd(a, b) = gcd(d, b) =

1.
Remark. Ryan Kim points out that in fact, (a, b) = (2n − 1, 2n + 1) is always a solution.

3
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

§1.2 USAMO 2017/2, proposed by Maria Monks

Available online at https://aops.com/community/p8108658.

Problem statement

Let m1 , m2 , . . . , mn be a collection of n positive integers, not necessarily distinct.

For any sequence of integers A = (a1 , . . . , an ) and any permutation w = w1 , . . . , wn
of m1 , . . . , mn , define an A-inversion of w to be a pair of entries wi , wj with i < j
for which one of the following conditions holds:

• ai ≥ wi > wj ,

• wj > ai ≥ wi , or

• wi > w j > a i .

Show that, for any two sequences of integers A = (a1 , . . . , an ) and B = (b1 , . . . , bn ),
and for any positive integer k, the number of permutations of m1 , . . . , mn having
exactly k A-inversions is equal to the number of permutations of m1 , . . . , mn having
exactly k B-inversions.

The following solution was posted by Michael Ren, and I think it is the most natural one
(since it captures all the combinatorial ideas using a q-generating function that is easier
to think about, and thus makes the problem essentially a long computation).
Denote by M our multiset of n positive integers. Define an inversion of a permutation to
be pair i < j with wi < wj (which is a (0, . . . , 0)-inversion in the problem statement); this
is the usual definition (see https://en.wikipedia.org/wiki/Inversion_(discrete_
mathematics)). So we want to show the number of A-inversions is equal to the number
of usual inversions. In what follows we count permutations on M with multiplicity: so
M = {1, 1, 2} still has 3! = 6 permutations.
We are going to do what is essentially recursion, but using generating functions in
a variable q to do our book-keeping. (Motivation: there’s no good closed form for the
number of inversions, but there’s a great generating function known — which is even
better for us, since we’re only trying to show two numbers are equal!) First, we prove
two claims.

Claim — For any positive integer n, the generating function for the number of
permutations of (1, 2, . . . , n) with exactly k inversions is

n!q := 1 · (1 + q) · (1 + q + q 2 ) · . . . (1 + q + · · · + q n−1 ).

Here we mean that the coefficient of q s above gives the number of permutations with
exactly s inversions.

Proof. This is an induction on n, with n = 1 being trivial. Suppose we choose the first
element to be i, with 1 ≤ i ≤ n. Then there will always be exactly i − 1 inversions
using the first element, so this contributes q i · (n − 1)!q . Summing 1 ≤ i ≤ n gives the
result.

Unfortunately, the main difficulty of the problem is that there are repeated elements,
which makes our notation much more horrific.

4
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

Let us define the following. We take our given multiset M of n positive integers, we
suppose the distinct numbers are θ1 < θ2 < · · · < θm . We let ei be the number of times
θi appears. Therefore the multiplicities ei should have sums

e1 + · · · + em = n

and m denotes the number of distinct elements. Finally, we let

q number inversions of σ
X
F (e1 , . . . , em ) =
permutations σ

be the associated generating function for the number of inversions. For example, the first
claim we proved says that F (1, . . . , 1) = n!q .

Claim — We have the explicit formula

m
Y ei !
F (e1 , . . . , em ) = n!q · .
ei !q
i=1

Proof. First suppose we perturb all the elements slightly, so that they are no longer equal.
Then the generating function would just be n!q .
Then, we undo the perturbations for each group, one at a time, and claim that we get
the above ei !q factor each time. Indeed, put the permutations into classes of e1 ! each
where permutations in the same classes differ only in the order of the perturbed θ1 ’s
(with the other n − e1 elements being fixed). Then there is a factor of e1 !q from each class,
owing to the slightly perturbed inversions we added within each class. So we remove that
factor and add e1 ! · q 0 instead. This accounts for the first term of the product.
Repeating this now with each term of the product implies the claim.

Thus we have the formula for the number of inversions in general. We wish to show
this also equals the generating function the number of A-inversions, for any fixed choice
of A. This will be an induction by n, with the base case being immediate.
For the inductive step, fix A, and assume the first element satisfies θk ≤ a1 < θk+1 (so
0 ≤ k ≤ m; we for convenience set θ0 = −∞ and θm = +∞). We count the permutations
based on what the first element θi of the permutation is. Then:
• Consider permutations starting with θi ∈ {θ1 , . . . , θk }. Then the number of inver-
sions which will use this first term is (e1 + · · · + ei−1 ) + (ek+1 + · · · + em ). Also, there
are ei ways to pick which θi gets used as the first term. So we get a contribution of

q e1 +···+ei−1 +(ek+1 +···+em ) · ei · F (e1 , . . . , ei − 1, . . . , em )

in this case (with inductive hypothesis to get the last F -term).

• Now suppose θi ∈ {θk+1 , . . . , θm }. Then the number of inversions which will use
this first term is ek+1 + · · · + ei−1 . Thus by a similar argument the contribution is

q ek+1 +···+ei−1 · ei · F (e1 , . . . , ei − 1, . . . , em ).

Therefore, to complete the problem it suffices to prove

k
X
q (e1 +···+ei−1 )+(ek+1 +···+em ) · ei · F (e1 , . . . , ei − 1, . . . , em )
i=1

5
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

m
X
+ q ek+1 +···+ei−1 · ei · F (e1 , . . . , ei − 1, . . . , em )
i=k+1
= F (e1 , . . . , em ).

Now, we see that

ei · F (e1 , . . . , ei − 1, . . . , em ) 1 + · · · + q ei −1 1 − q ei
= =
F (e1 , . . . , em ) 1 + q + · · · + q n−1 1 − qn

so it’s equivalent to show

k
X m
X
1 − q n = q ek+1 +···+em q e1 +···+ei−1 (1 − q ei ) + q ek+1 +···+ei−1 (1 − q ei )
i=1 i=k+1

which is clear, since the left summand telescopes to q ek+1 +···+em − q n and the right
summand telescopes to 1 − q ek+1 +···+em .

Remark. Technically, we could have skipped straight to the induction, without proving the
first two claims. However I think the solution reads more naturally this way.

6
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

§1.3 USAMO 2017/3, proposed by Evan Chen

Available online at https://aops.com/community/p8108375.

Problem statement

Let ABC be a scalene triangle with circumcircle Ω and incenter I. Ray AI meets
BC at D and Ω again at M ; the circle with diameter DM cuts Ω again at K.
Lines M K and BC meet at S, and N is the midpoint of IS. The circumcircles of
4KID and 4M AN intersect at points L1 and L2 . Prove that Ω passes through
the midpoint of either IL1 or IL2 .

Let W be the midpoint of BC, let X be the point on Ω opposite M . Observe that KD
passes through X, and thus lines BC, M K, XA concur at the orthocenter of 4DM X,
which we call S. Denote by IA the A-excenter of ABC.
Next, let E be the foot of the altitude from I to XIA ; observe that E lies on the
circle centered at M through I, B, C, IA . Then, S is the radical center of Ω and the
circles with diameter IX and IIA ; hence line SI passes through E; accordingly I is the
orthocenter of 4XSIA ; denote by L the foot from X to SIA .

I
N

S B D W C
T

K
L M

IA

We claim that this L lies on both the circumcircle of 4KID and 4M AN . It lies on
the circumcircle of 4M AN since this circle is the nine-point circle of 4XSIA . Also,
XD · XK = XW · XM = XA · XS = XI · XL, so KDIL are concyclic.
All that remains to show is that the midpoint T of IL lies on Ω. But this follows from
the fact that T M k LIA =⇒ ∠M T X = 90◦ , thus the problem is solved.

Remark. Some additional facts about this picture: the point T is the contact point of the
A-mixtilinear incircle (since it is collinear with X and I), while the point K is such that
AK is an A-symmedian (since KD and AD bisect ∠A and ∠K, say).

7
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

IA

M
B
L K

T D
C
N I

S IB A X IC

Remark. In fact, the point L is the Miquel point of cyclic quadrilateral IB IC BC (inscribed
in the circle with diameter IB IC ). This implies many of the properties that L has above. For
example, it directly implies that L lies on the circumcircles of triangles IA IB IC and BCIA ,
and that the point L lies on SIA (since S = BC ∩ IB IC ). For this reason, many students
found it easier to think about the problem in terms of 4IA IB IC rather than 4ABC.

8
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

§2 Solutions to Day 2
§2.1 USAMO 2017/4, proposed by Maria Monks
Available online at https://aops.com/community/p8117190.

Problem statement

Let P1 , P2 , . . . , P2n be 2n distinct points on the unit circle x2 + y 2 = 1, other than

(1, 0). Each point is colored either red or blue, with exactly n red points and n blue
points. Let R1 , R2 , . . . , Rn be any ordering of the red points. Let B1 be the nearest
blue point to R1 traveling counterclockwise around the circle starting from R1 . Then
let B2 be the nearest of the remaining blue points to R2 travelling counterclockwise
around the circle from R2 , and so on, until we have labeled all of the blue points B1 ,
. . . , Bn . Show that the number of counterclockwise arcs of the form Ri → Bi that
contain the point (1, 0) is independent of the way we chose the ordering R1 , . . . , Rn
of the red points.

We present two solutions, one based on swapping and one based on an invariant.

¶ First “local” solution by swapping two points Let 1 ≤ i < n be any index and
consider the two red points Ri and Ri+1 . There are two blue points Bi and Bi+1 associated
with them.

Claim — If we swap the locations of points Ri and Ri+1 then the new arcs Ri → Bi
and Ri+1 → Bi+1 will cover the same points.

Proof. Delete all the points R1 , . . . , Ri−1 and B1 , . . . , Bi−1 ; instead focus on the positions
of Ri and Ri+1 .
The two blue points can then be located in three possible ways: either 0, 1, or 2 of
them lie on the arc Ri → Ri+1 . For each of the cases below, we illustrate on the left the
locations of Bi and Bi+1 and the corresponding arcs in green; then on the right we show
the modified picture where Ri and Ri+1 have swapped. (Note that by hypothesis there
are no other blue points in the green arcs).

9
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

Bi+1 Bi Bi+1 Bi

Case 1 Ri+1 Ri Ri Ri+1

Bi Bi+1

Case 2 Ri+1 Ri Ri Ri+1

Bi+1 Bi

Case 3 Ri+1 Ri Ri Ri+1

Bi Bi+1 Bi Bi+1

Observe that in all cases, the number of arcs covering any given point on the circumference
is not changed. Consequently, this proves the claim.

Finally, it is enough to recall that any permutation of the red points can be achieved
by swapping consecutive points (put another way: (i i + 1) generates the permutation
group Sn ). This solves the problem.

Remark. This proof does not work if one tries to swap Ri and Rj if |i − j| 6= 1. For example
if we swapped Ri and Ri+2 then there are some issues caused by the possible presence of
the blue point Bi+1 in the green arc Ri+2 → Bi+2 .

¶ Second longer solution using an invariant Visually, if we draw all the segments
Ri → Bi then we obtain a set of n chords. Say a chord is inverted if satisfies the problem
condition, and stable otherwise. The problem contends that the number of stable/inverted
chords depends only on the layout of the points and not on the choice of chords.
−1 0

0 −1

(1, 0)

+1 0

0 −1

In fact we’ll describe the number of inverted chords explicitly. Starting from (1, 0) we
keep a running tally of R − B; in other words we start the counter at 0 and decrement

10
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

by 1 at each blue point and increment by 1 at each red point. Let x ≤ 0 be the lowest
number ever recorded. Then:

Claim — The number of inverted chords is −x (and hence independent of the

choice of chords).
This is by induction on n. I think the easiest thing is to delete chord R1 B1 ; note that
the arc cut out by this chord contains no blue points. So if the chord was stable certainly
no change to x. On the other hand, if the chord is inverted, then in particular the last
point before (1, 0) was red, and so x < 0. In this situation one sees that deleting the
chord changes x to x + 1, as desired.

11
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

§2.2 USAMO 2017/5, proposed by Ricky Liu

Available online at https://aops.com/community/p8117096.

Problem statement

Find all real numbers c > 0 such that there exists a labeling of the lattice points in
Z2 with positive integers for which:

• only finitely many distinct labels occur, and

• for each label i, the distance between any two points labeled i is at least ci .

√
The answer is c < 2. Here is a solution
√ with Calvin Deng.
The construction for any c < 2 can be done as follows. Checkerboard color the
lattice points and label√the black ones with 1. The white points then form a copy of
Z2 again scaled up by 2 so we can repeat the procedure with 2 on half the resulting
points. Continue this dyadic construction until a large N for which cN < 2 2 (N −1) , at
1

which point we can just label

√ all the points with
√ N.
I’ll now prove that c = 2 (and hence c ≥ 2) can’t be done.

Claim — It is impossible to fill a 2n × 2n square with labels not exceeding 2n.

The case n = 1 is clear. So now assume it’s true up to n − 1; and assume for contradiction
a 2n × 2n square S only contains labels up to 2n. (Of course every 2n−1 × 2n−1 square
contains an instance of a label at least 2n − 1.)

A
2 1 2 1

1 5 1 3 6

2 1 2 1

1 3 1 4

Now, we contend there are fewer than four copies of 2n:

Lemma
In a unit square, among any four points, two of these points have distance ≤ 1 apart.

Proof. Look at the four rays emanating from the origin and note that two of them have
included angle ≤ 90◦ .

12
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

So WLOG the northwest quadrant has no 2n’s. Take a 2n − 1 in the northwest and
draw a square of size 2n−1 × 2n−1 directly right of it (with its top edge coinciding with
the top of S). Then A can’t contain 2n − 1, so it must contain a 2n label; that 2n label
must be in the northeast quadrant.
Then we define a square B of size 2n−1 × 2n−1 as follows. If 2n − 1 is at least as high
2n, let B be a 2n−1 × 2n−1 square which touches 2n − 1 north and is bounded east by
2n. Otherwise let B be the square that touches 2n − 1 west and is bounded north by 2n.
We then observe B can neither have 2n − 1 nor 2n in it, contradiction.

Remark. To my knowledge, essentially all density arguments fail because of hexagonal

lattice packing.

13
USAMO 2017 Solution Notes web.evanchen.cc, updated 2 June 2023

§2.3 USAMO 2017/6, proposed by Titu Andreescu

Available online at https://aops.com/community/p8117097.

Problem statement

Find the minimum possible value of

a b c d
+ 3 + 3 + 3
b3 +4 c +4 d +4 a +4
given that a, b, c, d are nonnegative real numbers such that a + b + c + d = 4.

The minimum 23 is achieved at (a, b, c, d) = (2, 2, 0, 0) and cyclic permutations.

The problem is an application of the tangent line trick: we observe the miraculous
identity
1 1 b
3
≥ −
b +4 4 12
since 12 − (3 − b)(b3 + 4) = b(b + 1)(b − 2)2 ≥ 0. Moreover,
 2
(a + c) + (b + d)
ab + bc + cd + da = (a + c)(b + d) ≤ = 4.
2

Thus
X a a + b + c + d ab + bc + cd + da 1 2
≥ − ≥1− = .
cyc
b3 +4 4 12 3 3

Remark. The main interesting bit is the equality at (a, b, c, d) = (2, 2, 0, 0). P
This is the
main motivation for trying tangent line trick, since a lower bound of the form a(1 − λb)
preserves the unusual equality case above. Thus one takes the tangent at b = 2 which
miraculously passes through the point (0, 1/4) as well.

14