% © Evan Chen
% Downloaded from https://web.evanchen.cc/
\documentclass[11pt]{scrartcl}
\usepackage[sexy]{evan}
\ihead{\footnotesize\textbf{\thetitle}}
\ohead{\footnotesize\href{http://web.evanchen.cc}{\ttfamily web.evanchen.cc},
updated \today}
\title{USAMO 2017 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2017 USAMO.
The ideas of the solution are a mix of my own work,
the solutions provided by the competition organizers,
and solutions found by the community.
However, all the writing is maintained by me.
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 $\mathbb{R}$ denote the set of real numbers''
are typically omitted entirely.
Corrections and comments are welcome!
\end{abstract}
\tableofcontents
\newpage
\addtocounter{section}{-1}
\section{Problems}
\begin{enumerate}[\bfseries 1.]
\item %% Problem 1
Prove that there exist infinitely many pairs of
relatively prime positive integers $a,b > 1$
for which $a+b$ divides $a^b+b^a$.
\item %% Problem 2
Let $m_1$, $m_2$, \dots, $m_n$ be a collection of $n$ positive integers,
not necessarily distinct.
For any sequence of integers $A = (a_1, \dots, a_n)$
and any permutation $w = w_1, \dots, w_n$ of $m_1, \dots, m_n$,
define an $A$-inversion of $w$ to be a pair of
entries $w_i, w_j$ with $i < j$ for which
one of the following conditions holds:
\begin{itemize}
\ii $a_i \ge w_i > w_j$,
\ii $w_j > a_i \ge w_i$, or
\ii $w_i > w_j > a_i$.
\end{itemize}
Show that, for any two sequences of integers
$A = (a_1, \dots, a_n)$ and $B = (b_1, \dots, b_n)$,
and for any positive integer $k$, the number of permutations
of $m_1, \dots, m_n$ having exactly $k$ $A$-inversions
is equal to the number of permutations of $m_1, \dots, m_n$
having exactly $k$ $B$-inversions.
\item %% Problem 3
Let $ABC$ be a scalene triangle with circumcircle $\Omega$ and incenter $I$.
Ray $AI$ meets $\ol{BC}$ at $D$ and $\Omega$ again at $M$;
the circle with diameter $\ol{DM}$ cuts $\Omega$ again at $K$.
Lines $MK$ and $BC$ meet at $S$, and $N$ is the midpoint of $\ol{IS}$.
The circumcircles of $\triangle KID$ and $\triangle MAN$
intersect at points $L_1$ and $L_2$.
Prove that $\Omega$ passes through the midpoint of either $\ol{IL_1}$ or $\ol{IL_2}$.
\item %% Problem 4
Let $P_1$, $P_2$, \dots, $P_{2n}$ be $2n$ distinct points on the
unit circle $x^2+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 $R_1$, $R_2$, \dots, $R_n$ be any ordering of the red points.
Let $B_1$ be the nearest blue point to $R_1$ traveling
counterclockwise around the circle starting from $R_1$.
Then let $B_2$ be the nearest of the remaining blue points to $R_2$
travelling counterclockwise around the circle from $R_2$, and so on,
until we have labeled all of the blue points $B_1$, \dots, $B_n$.
Show that the number of counterclockwise arcs of the form $R_i \to B_i$
that contain the point $(1,0)$ is independent of the way we chose the
ordering $R_1$, \dots, $R_n$ of the red points.
\item %% Problem 5
Find all real numbers $c > 0$ such that there exists a labeling
of the lattice points in $\ZZ^2$ with positive integers for which:
\begin{itemize}
\ii only finitely many distinct labels occur, and
\ii for each label $i$, the distance between any two points
labeled $i$ is at least $c^i$.
\end{itemize}
\item %% Problem 6
Find the minimum possible value of
\[ \frac{a}{b^3+4} + \frac{b}{c^3+4}
+ \frac{c}{d^3+4} + \frac{d}{a^3+4} \]
given that $a$, $b$, $c$, $d$ are nonnegative real numbers
such that $a+b+c+d=4$.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{USAMO 2017/1, proposed by Gregory Galperin}
\textsl{Available online at \url{https://aops.com/community/p8108366}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Prove that there exist infinitely many pairs of
relatively prime positive integers $a,b > 1$
for which $a+b$ divides $a^b+b^a$.
\end{mdframed}
One construction: let $d \equiv 1 \pmod 4$, $d > 1$.
Let $x = \frac{d^d+2^d}{d+2}$. Then set
\[ a = \frac{x+d}{2}, \qquad
b = \frac{x-d}{2}. \]
To see this works, first check that $b$ is odd and $a$ is even.
Let $d = a-b$ be odd.
Then:
\begin{align*}
a+b \mid a^b+b^a &\iff
(-b)^b + b^a \equiv 0 \pmod{a+b} \\
&\iff b^{a-b} \equiv 1 \pmod{a+b} \\
&\iff b^d \equiv 1 \pmod{d+2b} \\
&\iff (-2)^d \equiv d^d \pmod{d+2b} \\
&\iff d+2b \mid d^d + 2^d.
\end{align*}
So it would be enough that
\[ d+2b = \frac{d^d+2^d}{d+2}
\implies b = \half \left( \frac{d^d+2^d}{d+2} - d \right) \]
which is what we constructed.
Also, since $\gcd(x,d) = 1$ it follows $\gcd(a,b) = \gcd(d,b) = 1$.
\begin{remark*}
Ryan Kim points out that in fact,
$(a,b) = (2n-1,2n+1)$ is always a solution.
\end{remark*}
\pagebreak
\subsection{USAMO 2017/2, proposed by Maria Monks}
\textsl{Available online at \url{https://aops.com/community/p8108658}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $m_1$, $m_2$, \dots, $m_n$ be a collection of $n$ positive integers,
not necessarily distinct.
For any sequence of integers $A = (a_1, \dots, a_n)$
and any permutation $w = w_1, \dots, w_n$ of $m_1, \dots, m_n$,
define an $A$-inversion of $w$ to be a pair of
entries $w_i, w_j$ with $i < j$ for which
one of the following conditions holds:
\begin{itemize}
\ii $a_i \ge w_i > w_j$,
\ii $w_j > a_i \ge w_i$, or
\ii $w_i > w_j > a_i$.
\end{itemize}
Show that, for any two sequences of integers
$A = (a_1, \dots, a_n)$ and $B = (b_1, \dots, b_n)$,
and for any positive integer $k$, the number of permutations
of $m_1, \dots, m_n$ having exactly $k$ $A$-inversions
is equal to the number of permutations of $m_1, \dots, m_n$
having exactly $k$ $B$-inversions.
\end{mdframed}
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 \emph{inversion} of a permutation to be pair $i < j$
with $w_i < w_j$ (which is a $(0,\dots,0)$-inversion in the problem statement);
this is the usual definition
(see \url{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.
\begin{claim*}
For any positive integer $n$,
the generating function for the number of permutations
of $(1, 2, \dots, n)$ with exactly $k$ inversions is
\[ n!_q \coloneqq 1 \cdot (1+q) \cdot (1+q+q^2) \cdot \dots (1+q+\dots+q^{n-1}). \]
\end{claim*}
Here we mean that the coefficient of $q^s$ above
gives the number of permutations with exactly $s$ inversions.
\begin{proof}
This is an induction on $n$, with $n=1$ being trivial.
Suppose we choose the first element to be $i$, with $1 \le i \le n$.
Then there will always be exactly $i-1$ inversions
using the first element,
so this contributes $q^i \cdot (n-1)!_q$.
Summing $1 \le i \le n$ gives the result.
\end{proof}
Unfortunately, the main difficulty of the problem
is that there are repeated elements,
which makes our notation much more horrific.
Let us define the following.
We take our given multiset $M$ of $n$ positive integers,
we suppose the distinct numbers are
$\theta_1 < \theta_2 < \dots < \theta_m$.
We let $e_i$ be the number of times $\theta_i$ appears.
Therefore the multiplicities $e_i$ should have sums
\[ e_1 + \dots + e_m = n \]
and $m$ denotes the number of distinct elements.
Finally, we let
\[ F(e_1, \dots, e_m)
= \sum_{\text{permutations } \sigma}
q^{\text{number inversions of } \sigma} \]
be the associated generating function for the number of inversions.
For example, the first claim we proved says that $F(1, \dots, 1) = n!_q$.
\begin{claim*}
We have the explicit formula
\[ F(e_1, \dots, e_m) = n!_q \cdot \prod_{i=1}^m \frac{e_i!}{e_i!_q}. \]
\end{claim*}
\begin{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 $e_i!_q$ factor each time.
Indeed, put the permutations into classes of $e_1!$ each
where permutations in the same classes differ
only in the order of the perturbed $\theta_1$'s
(with the other $n-e_1$ elements being fixed).
Then there is a factor of $e_1!_q$ from each class,
owing to the slightly perturbed inversions we added within each class.
So we remove that factor and add $e_1! \cdot q^0$ instead.
This accounts for the first term of the product.
Repeating this now with each term of the product implies the claim.
\end{proof}
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
$\theta_k \le a_1 < \theta_{k+1}$ (so $0 \le k \le m$;
we for convenience set $\theta_0 = -\infty$ and $\theta_m = +\infty$).
We count the permutations based on what the first element
$\theta_i$ of the permutation is.
Then:
\begin{itemize}
\ii Consider permutations starting with
$\theta_i \in \left\{ \theta_1, \dots, \theta_k \right\}$.
Then the number of inversions which will
use this first term is $(e_1 + \dots + e_{i-1})
+ (e_{k+1} + \dots + e_m)$.
Also, there are $e_i$ ways to pick which
$\theta_i$ gets used as the first term.
So we get a contribution of
\[ q^{e_1 + \dots + e_{i-1} + (e_{k+1} + \dots + e_m)}
\cdot e_i \cdot F(e_1, \dots, e_i-1, \dots, e_m) \]
in this case
(with inductive hypothesis to get the last $F$-term).
\ii Now suppose $\theta_i \in \left\{ \theta_{k+1}, \dots, \theta_m \right\}$.
Then the number of inversions which will
use this first term is $e_{k+1} + \dots + e_{i-1}$.
Thus by a similar argument the contribution is
\[ q^{e_{k+1} + \dots + e_{i-1}}
\cdot e_i \cdot F(e_1, \dots, e_i-1, \dots, e_m). \]
\end{itemize}
Therefore, to complete the problem it suffices to prove
\begin{align*}
&\phantom+ \sum_{i=1}^k q^{(e_1 + \dots + e_{i-1}) + (e_{k+1} + \dots + e_m)}
\cdot e_i \cdot F(e_1, \dots, e_i-1, \dots, e_m) \\
&+ \sum_{i=k+1}^m q^{e_{k+1} + \dots + e_{i-1}}
\cdot e_i \cdot F(e_1, \dots, e_i-1, \dots, e_m) \\
&= F(e_1, \dots, e_m).
\end{align*}
Now, we see that
\[ \frac{e_i \cdot F(e_1, \dots, e_i-1, \dots, e_m)}{F(e_1, \dots, e_m)}
= \frac{1+\dots+q^{e_i-1}}{1+q+\dots+q^{n-1}}
= \frac{1-q^{e_i}}{1-q^n} \]
so it's equivalent to show
\[ 1-q^n
= q^{e_{k+1} + \dots + e_m} \sum_{i=1}^k q^{e_1 + \dots + e_{i-1}}(1-q^{e_i})
+ \sum_{i=k+1}^m q^{e_{k+1} + \dots + e_{i-1}} (1-q^{e_i})
\]
which is clear,
since the left summand telescopes to
$q^{e_{k+1}+\dots+e_m} - q^n$
and the right summand telescopes to
$1 - q^{e_{k+1}+\dots+e_m}$.
\begin{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.
\end{remark*}
\pagebreak
\subsection{USAMO 2017/3, proposed by Evan Chen}
\textsl{Available online at \url{https://aops.com/community/p8108375}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be a scalene triangle with circumcircle $\Omega$ and incenter $I$.
Ray $AI$ meets $\ol{BC}$ at $D$ and $\Omega$ again at $M$;
the circle with diameter $\ol{DM}$ cuts $\Omega$ again at $K$.
Lines $MK$ and $BC$ meet at $S$, and $N$ is the midpoint of $\ol{IS}$.
The circumcircles of $\triangle KID$ and $\triangle MAN$
intersect at points $L_1$ and $L_2$.
Prove that $\Omega$ passes through the midpoint of either $\ol{IL_1}$ or $\ol{IL_2}$.
\end{mdframed}
Let $W$ be the midpoint of $\ol{BC}$,
let $X$ be the point on $\Omega$ opposite $M$.
Observe that $\ol{KD}$ passes through $X$,
and thus lines $BC$, $MK$, $XA$ concur at
the orthocenter of $\triangle DMX$, which we call $S$.
Denote by $I_A$ the $A$-excenter of $ABC$.
Next, let $E$ be the foot of the altitude from $I$ to $\ol{XI_A}$;
observe that $E$ lies on the circle centered at $M$
through $I$, $B$, $C$, $I_A$.
Then, $S$ is the radical center of $\Omega$
and the circles with diameter $\ol{IX}$ and $\ol{II_A}$;
hence line $SI$ passes through $E$;
accordingly $I$ is the orthocenter of $\triangle XSI_A$;
denote by $L$ the foot from $X$ to $\ol{SI_A}$.
\begin{center}
\begin{asy}
size(10cm);
pair A = dir(160);
pair B = dir(210);
pair C = dir(330);
pair I = incenter(A, B, C);
pair D = extension(A, I, B, C);
pair M = circumcenter(B, I, C);
pair I_A = 2*M-I;
pair X = -M;
pair K = foot(M, D, X);
pair S = extension(M, K, B, C);
pair N = midpoint(I--S);
pair W = midpoint(B--C);
pair E = foot(I, X, I_A);
draw(A--B--C--cycle, orange);
filldraw(unitcircle, opacity(0.1)+lightred, orange);
filldraw(CP(M, I), opacity(0.1)+yellow, olive);
draw(A--I_A, orange);
draw(M--X, orange);
draw(S--E, olive);
draw(X--I_A, olive);
draw(B--S, orange);
pair L = foot(X, I_A, S);
draw(M--S--X--cycle, heavyred+1);
draw(X--K, heavyred+1);
draw(A--M, heavyred+1);
draw(S--W, heavyred+1);
draw(S--I_A, orange);
draw(circumcircle(K, I, D), palered+1);
filldraw(circumcircle(M, A, N), opacity(0.1)+yellow, palered+1);
draw(X--L, orange+1);
pair T = midpoint(I--L);
draw(T--M, orange);
dot("$A$", A, dir(150));
dot("$B$", B, dir(B));
dot("$C$", C, dir(-10));
dot("$I$", I, dir(I));
dot("$D$", D, dir(D));
dot("$M$", M, dir(M));
dot("$I_A$", I_A, dir(I_A));
dot("$X$", X, dir(X));
dot("$K$", K, dir(K));
dot("$S$", S, dir(S));
dot("$N$", N, dir(135));
dot("$W$", W, dir(-45));
dot("$E$", E, dir(45));
dot("$L$", L, dir(L));
dot("$T$", T, dir(T));
/* Source generated by TSQ:
!size(10cm);
A = dir 160 R150
B = dir 210
C = dir 330 R-10
I = incenter A B C
D = extension A I B C
M = circumcenter B I C
I_A = 2*M-I
X = -M
K = foot M D X
S = extension M K B C
N = midpoint I--S R135
W = midpoint B--C R-45
E = foot I X I_A R45
A--B--C--cycle orange
unitcircle 0.1 lightred / orange
CP M I 0.1 yellow / olive
A--I_A orange
M--X orange
S--E olive
X--I_A olive
B--S orange
L = foot X I_A S
M--S--X--cycle heavyred+1
X--K heavyred+1
A--M heavyred+1
S--W heavyred+1
S--I_A orange
circumcircle K I D palered+1
circumcircle M A N 0.1 yellow / palered+1
X--L orange+1
T = midpoint I--L
T--M orange
*/
\end{asy}
\end{center}
We claim that this $L$ lies on
both the circumcircle of $\triangle KID$ and $\triangle MAN$.
It lies on the circumcircle of $\triangle MAN$
since this circle is the nine-point circle of $\triangle XSI_A$.
Also, $XD \cdot XK = XW \cdot XM = XA \cdot XS = XI \cdot XL$,
so $KDIL$ are concyclic.
%For the other, note that $\triangle MWI \sim \triangle MIX$,
%according to which $\angle IWM = \angle MIX = 180^{\circ} - \angle LIM = 180^{\circ} - \angle MLI$,
%enough to imply that quadrilateral $MWIL$ is cyclic.
%But lines $IL$, $DK$, and $WM$ meet at $X$, implying the conclusion.
All that remains to show is that the
midpoint $T$ of $\ol{IL}$ lies on $\Omega$.
But this follows from the fact that
$\ol{TM} \parallel \ol{LI_A} \implies \angle MTX = 90^{\circ}$,
thus the problem is solved.
\begin{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 $\ol{AK}$ is an $A$-symmedian
(since $\ol{KD}$ and $\ol{AD}$ bisect $\angle A$ and $\angle K$, say).
\end{remark*}
\begin{center}
\begin{asy}
pair I_A = dir(115);
pair I_B = dir(215);
pair I_C = dir(325);
pair A = foot(I_A, I_B, I_C);
pair B = foot(I_B, I_C, I_A);
pair C = foot(I_C, I_A, I_B);
pair X = midpoint(I_B--I_C);
pair S = extension(B, C, I_B, I_C);
pair I = incenter(A, B, C);
pair L = extension(X, I, S, I_A);
pair D = extension(A, I, B, C);
pair M = midpoint(I--I_A);
pair K = foot(M, D, X);
pair N = midpoint(I--S);
draw(I_A--I_B--I_C--cycle, heavycyan);
filldraw(circumcircle(I_A, I_B, I_C), opacity(0.1)+palered, heavycyan);
filldraw(circumcircle(A, B, C), opacity(0.1)+orange, orange);
draw(A--B--C--cycle, orange);
draw(S--I_A, orange);
draw(S--I, olive);
draw(S--I_B, heavycyan);
draw(A--I_A, heavycyan);
filldraw(circumcircle(K, I, D), opacity(0.07)+yellow, palered+1);
filldraw(circumcircle(M, A, N), opacity(0.07)+yellow, palered+1);
draw(X--L, orange+1);
pair T = midpoint(I--L);
draw(M--X, olive);
draw(K--X, olive);
draw(M--S, olive);
draw(X--I_A, heavycyan);
draw(S--C, orange);
filldraw(circumcircle(I, B, C), opacity(0.1)+palecyan, heavycyan);
dot("$I_A$", I_A, dir(I_A));
dot("$I_B$", I_B, dir(I_B));
dot("$I_C$", I_C, dir(I_C));
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$X$", X, dir(X));
dot("$S$", S, dir(S));
dot("$I$", I, dir(I));
dot("$L$", L, dir(L));
dot("$D$", D, dir(D));
dot("$M$", M, dir(M));
dot("$K$", K, dir(K));
dot("$N$", N, dir(80));
dot("$T$", T, dir(T));
/* TSQ Source:
I_A = dir 115
I_B = dir 215
I_C = dir 325
A = foot I_A I_B I_C
B = foot I_B I_C I_A
C = foot I_C I_A I_B
X = midpoint I_B--I_C
S = extension B C I_B I_C
I = incenter A B C
L = extension X I S I_A
D = extension A I B C
M = midpoint I--I_A
K = foot M D X
N = midpoint I--S R80
I_A--I_B--I_C--cycle heavycyan
circumcircle I_A I_B I_C 0.1 palered / heavycyan
circumcircle A B C 0.1 orange / orange
A--B--C--cycle orange
S--I_A orange
S--I olive
S--I_B heavycyan
A--I_A heavycyan
circumcircle K I D 0.07 yellow / palered+1
circumcircle M A N 0.07 yellow / palered+1
X--L orange+1
T = midpoint I--L
M--X olive
K--X olive
M--S olive
X--I_A heavycyan
S--C orange
circumcircle I B C 0.1 palecyan / heavycyan
*/
\end{asy}
\end{center}
\begin{remark*}
In fact, the point $L$ is the Miquel point of cyclic quadrilateral
$I_B I_C B C$ (inscribed in the circle with diameter $\ol{I_B I_C}$).
This implies many of the properties that $L$ has above.
For example, it directly implies that $L$ lies on the circumcircles
of triangles $I_A I_B I_C$ and $BCI_A$,
and that the point $L$ lies on $\ol{SI_A}$
(since $S = \ol{BC} \cap \ol{I_B I_C}$).
For this reason, many students found it easier to think about
the problem in terms of $\triangle I_A I_B I_C$ rather than $\triangle ABC$.
\end{remark*}
\pagebreak
\section{Solutions to Day 2}
\subsection{USAMO 2017/4, proposed by Maria Monks}
\textsl{Available online at \url{https://aops.com/community/p8117190}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $P_1$, $P_2$, \dots, $P_{2n}$ be $2n$ distinct points on the
unit circle $x^2+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 $R_1$, $R_2$, \dots, $R_n$ be any ordering of the red points.
Let $B_1$ be the nearest blue point to $R_1$ traveling
counterclockwise around the circle starting from $R_1$.
Then let $B_2$ be the nearest of the remaining blue points to $R_2$
travelling counterclockwise around the circle from $R_2$, and so on,
until we have labeled all of the blue points $B_1$, \dots, $B_n$.
Show that the number of counterclockwise arcs of the form $R_i \to B_i$
that contain the point $(1,0)$ is independent of the way we chose the
ordering $R_1$, \dots, $R_n$ of the red points.
\end{mdframed}
We present two solutions, one based on
swapping and one based on an invariant.
\paragraph{First ``local'' solution by swapping two points.}
Let $1 \le i < n$ be any index and consider the two red points
$R_i$ and $R_{i+1}$.
There are two blue points $B_i$ and $B_{i+1}$ associated with them.
\begin{claim*}
If we swap the locations of points $R_i$ and $R_{i+1}$ then
the new arcs $R_i \to B_i$ and $R_{i+1} \to B_{i+1}$
will cover the same points.
\end{claim*}
\begin{proof}
Delete all the points $R_1$, \dots, $R_{i-1}$
and $B_1$, \dots, $B_{i-1}$;
instead focus on the positions of $R_i$ and $R_{i+1}$.
The two blue points can then be located in three possible ways:
either $0$, $1$, or $2$ of them lie on the arc $R_i \to R_{i+1}$.
For each of the cases below, we illustrate on the left
the locations of $B_i$ and $B_{i+1}$
and the corresponding arcs in green;
then on the right we show the modified picture
where $R_i$ and $R_{i+1}$ have swapped.
(Note that by hypothesis there are no other blue points in the green arcs).
\begin{center}
\begin{asy}
unitsize(1cm);
pair O = (0,0);
picture init(bool flip) {
picture pic;
draw(pic, unitcircle);
if (flip) {
dot(pic, "$R_{i}$", dir(0), dir(0), red);
dot(pic, "$R_{i+1}$", dir(180), dir(180), red);
}
else {
dot(pic, "$R_{i+1}$", dir(0), dir(0), red);
dot(pic, "$R_{i}$", dir(180), dir(180), red);
}
return pic;
}
picture L1 = init(true);
picture L2 = init(true);
picture L3 = init(true);
picture R1 = init(false);
picture R2 = init(false);
picture R3 = init(false);
real r = 0.8;
real s = 0.9;
// Case 1
dot(L1, "$B_i$", dir(60), dir(60), blue);
dot(L1, "$B_{i+1}$", dir(120), dir(120), blue);
dot(R1, "$B_i$", dir(60), dir(60), blue);
dot(R1, "$B_{i+1}$", dir(120), dir(120), blue);
draw(L1, arc(O, r, 0, 60), deepgreen, EndArrow(TeXHead));
draw(L1, arc(O, s, 180, 480), deepgreen, EndArrow(TeXHead));
draw(R1, arc(O, r, 180, 420), deepgreen, EndArrow(TeXHead));
draw(R1, arc(O, s, 0, 120), deepgreen, EndArrow(TeXHead));
dot(L1, dir(140), blue);
dot(L1, dir(150), blue);
dot(R1, dir(140), blue);
dot(R1, dir(150), blue);
// Case 2
dot(L2, "$B_i$", dir(90), dir(90), blue);
dot(L2, "$B_{i+1}$", dir(270), dir(270), blue);
dot(R2, "$B_i$", dir(270), dir(270), blue);
dot(R2, "$B_{i+1}$", dir(90), dir(90), blue);
draw(L2, arc(O, s, 0, 90), deepgreen, EndArrow(TeXHead));
draw(L2, arc(O, s, 180, 270), deepgreen, EndArrow(TeXHead));
draw(R2, arc(O, s, 180, 270), deepgreen, EndArrow(TeXHead));
draw(R2, arc(O, s, 0, 90), deepgreen, EndArrow(TeXHead));
dot(L2, dir(128), blue);
dot(L2, dir(155), blue);
dot(R2, dir(128), blue);
dot(R2, dir(155), blue);
dot(L2, dir(297), blue);
dot(L2, dir(335), blue);
dot(R2, dir(297), blue);
dot(R2, dir(335), blue);
// Case 3
dot(L3, "$B_i$", dir(240), dir(240), blue);
dot(L3, "$B_{i+1}$", dir(300), dir(300), blue);
dot(R3, "$B_i$", dir(240), dir(240), blue);
dot(R3, "$B_{i+1}$", dir(300), dir(300), blue);
draw(L3, arc(O, r, 0, 240), deepgreen, EndArrow(TeXHead));
draw(L3, arc(O, s, 180, 300), deepgreen, EndArrow(TeXHead));
draw(R3, arc(O, r, 180, 240), deepgreen, EndArrow(TeXHead));
draw(R3, arc(O, s, 0, 300), deepgreen, EndArrow(TeXHead));
dot(L3, dir(328), blue);
dot(L3, dir(342), blue);
dot(R3, dir(328), blue);
dot(R3, dir(342), blue);
real t = 3.5;
add(shift(0,0)*L1);
add(shift(t,0)*R1);
add(shift(0,-t)*L2);
add(shift(t,-t)*R2);
add(shift(0,-2*t)*L3);
add(shift(t,-2*t)*R3);
label("Case 1", (-2.5,0));
label("Case 2", (-2.5,-t));
label("Case 3", (-2.5,-2*t));
\end{asy}
\end{center}
Observe that in all cases, the number of arcs covering
any given point on the circumference is not changed.
Consequently, this proves the claim.
\end{proof}
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 $S_n$).
This solves the problem.
\begin{remark*}
This proof does \emph{not} work if one tries to swap
$R_i$ and $R_j$ if $|i-j| \neq 1$.
For example if we swapped $R_i$ and $R_{i+2}$
then there are some issues caused by the
possible presence of the blue point $B_{i+1}$
in the green arc $R_{i+2} \to B_{i+2}$.
\end{remark*}
\paragraph{Second longer solution using an invariant.}
Visually, if we draw all the segments $R_i \to B_i$
then we obtain a set of $n$ chords.
Say a chord is \emph{inverted} if satisfies the problem condition,
and \emph{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.
\begin{center}
\begin{asy}
size(6cm);
pair A(int i) { return dir(22.5+45*i); }
draw(unitcircle, grey);
dot("$(1,0)$", dir(0), dir(0));
dotfactor *= 2;
draw(A(7)--A(0), EndArrow, Margins);
draw(A(1)--A(2), EndArrow, Margins);
draw(A(3)--A(5), EndArrow, Margins);
draw(A(4)--A(6), EndArrow, Margins);
dot("$-1$", A(0), A(0), blue);
dot("$0$", A(1), A(1), red);
dot("$-1$", A(2), A(2), blue);
dot("$0$", A(3), A(3), red);
dot("$+1$", A(4), A(4), red);
dot("$0$", A(5), A(5), blue);
dot("$-1$", A(6), A(6), blue);
dot("$0$", A(7), A(7), red);
\end{asy}
\end{center}
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 by $1$ at each
blue point and increment by $1$ at each red point.
Let $x \le 0$ be the lowest number ever recorded. Then:
\begin{claim*}
The number of inverted chords is $-x$
(and hence independent of the choice of chords).
\end{claim*}
This is by induction on $n$.
I think the easiest thing is to delete chord $R_1 B_1$;
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.
\pagebreak
\subsection{USAMO 2017/5, proposed by Ricky Liu}
\textsl{Available online at \url{https://aops.com/community/p8117096}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all real numbers $c > 0$ such that there exists a labeling
of the lattice points in $\ZZ^2$ with positive integers for which:
\begin{itemize}
\ii only finitely many distinct labels occur, and
\ii for each label $i$, the distance between any two points
labeled $i$ is at least $c^i$.
\end{itemize}
\end{mdframed}
The answer is $c < \sqrt2$. Here is a solution with Calvin Deng.
The construction for any $c < \sqrt 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 $\ZZ^2$ again
scaled up by $\sqrt 2$ so we can repeat the procedure with $2$
on half the resulting points.
Continue this dyadic construction until a large $N$
for which $c^N < 2^{\half (N-1)}$,
at which point we can just label all the points with $N$.
I'll now prove that $c = \sqrt 2$ (and hence $c \ge \sqrt 2$) can't be done.
\begin{claim*}
It is impossible to fill a $2^n \times 2^n$ square
with labels not exceeding $2n$.
\end{claim*}
The case $n = 1$ is clear.
So now assume it's true up to $n-1$;
and assume for contradiction a $2^n \times 2^n$ square
$S$ only contains labels up to $2n$.
(Of course every $2^{n-1} \times 2^{n-1}$ square
contains an instance of a label at least $2n-1$.)
\begin{center}
\begin{asy}
unitsize(0.75cm);
for (int i=0; i<=8; ++i) {
if ((i!=0) && (i!=4) && (i!=8)) {
draw( (0,i)--(8,i), grey );
draw( (i,0)--(i,8), grey );
}
else {
draw( (0,i)--(8,i), black+1 );
draw( (i,0)--(i,8), black+1 );
}
}
filldraw( box((2.1,4.1),(5.9,7.9)), opacity(0.2)+palered, red+1 );
filldraw( box((1.1,2.1),(4.9,5.9)), opacity(0.2)+lightgreen, blue+1 );
fill(box((0,4),(4,8)), opacity(0.1)+lightcyan);
label("$A$", (3.5,8), dir(90), red);
label("$B$", (2.5,2), dir(-90), blue);
label("$2$", (0.5,7.5));
label("$1$", (1.5,7.5));
label("$2$", (2.5,7.5));
label("$1$", (3.5,7.5));
label("$1$", (0.5,6.5));
label("$5$", (1.5,6.5), red);
label("$1$", (2.5,6.5));
label("$3$", (3.5,6.5));
label("$2$", (0.5,5.5));
label("$1$", (1.5,5.5));
label("$2$", (2.5,5.5));
label("$1$", (3.5,5.5));
label("$1$", (0.5,4.5));
label("$3$", (1.5,4.5));
label("$1$", (2.5,4.5));
label("$4$", (3.5,4.5));
label("$6$", (5.5,6.5), blue);
\end{asy}
\end{center}
Now, we contend there are fewer than four copies of $2n$:
\begin{lemma*}
In a unit square, among any four points,
two of these points have distance $\le 1$ apart.
\end{lemma*}
\begin{proof}
Look at the four rays emanating from the origin and note
that two of them have included angle $\le 90\dg$.
\end{proof}
So WLOG the northwest quadrant has no $2n$'s.
Take a $2n-1$ in the northwest and draw a square of size $2^{n-1} \times 2^{n-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 $2^{n-1} \times 2^{n-1}$ as follows.
If $2n-1$ is at least as high $2n$, let $B$ be a $2^{n-1} \times 2^{n-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.
\begin{remark*}
To my knowledge, essentially all density arguments fail
because of hexagonal lattice packing.
\end{remark*}
\pagebreak
\subsection{USAMO 2017/6, proposed by Titu Andreescu}
\textsl{Available online at \url{https://aops.com/community/p8117097}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find the minimum possible value of
\[ \frac{a}{b^3+4} + \frac{b}{c^3+4}
+ \frac{c}{d^3+4} + \frac{d}{a^3+4} \]
given that $a$, $b$, $c$, $d$ are nonnegative real numbers
such that $a+b+c+d=4$.
\end{mdframed}
The minimum $\frac23$ 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
\[ \frac{1}{b^3+4} \ge \frac14 - \frac{b}{12} \]
since $12-(3-b)(b^3+4) = b(b+1)(b-2)^2 \ge 0$.
Moreover,
\[ ab+bc+cd+da = (a+c)(b+d)
\le \left( \frac{(a+c)+(b+d)}{2} \right)^2 = 4. \]
Thus
\[ \sum_{\text{cyc}} \frac{a}{b^3+4}
\ge \frac{a+b+c+d}{4} - \frac{ab+bc+cd+da}{12}
\ge 1 - \frac13 = \frac23. \]
\begin{remark*}
The main interesting bit is the equality at $(a,b,c,d) = (2,2,0,0)$.
This is the main motivation for trying tangent line trick,
since a lower bound of the form $\sum a(1-\lambda 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.
\end{remark*}
\pagebreak
\end{document}