% © 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{IMO 2013 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2013 IMO.
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 $\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
Let $k$ and $n$ be positive integers.
Prove that there exist positive integers $m_1$, \dots, $m_k$
such that
\[ 1 + \frac{2^k-1}{n}
= \left( 1 + \frac{1}{m_1} \right)
\left( 1 + \frac{1}{m_2} \right)
\dots
\left( 1 + \frac{1}{m_k} \right).
\]
\item %% Problem 2
A configuration of $4027$ points in the plane is called
\emph{Colombian} if it consists of $2013$ red points and $2014$ blue points,
and no three of the points of the configuration are collinear.
By drawing some lines, the plane is divided into several regions.
An arrangement of lines is \emph{good} for a Colombian configuration
if the following two conditions are satisfied:
\begin{enumerate}
\ii[(i)] No line passes through any point of the configuration.
\ii[(ii)] No region contains points of both colors.
\end{enumerate}
Find the least value of $k$ such that for any Colombian configuration
of $4027$ points, there is a good arrangement of $k$ lines.
\item %% Problem 3
Let the excircle of triangle $ABC$ opposite
the vertex $A$ be tangent to the side $BC$ at the point $A_1$.
Define the points $B_1$ on $CA$ and $C_1$ on $AB$ analogously,
using the excircles opposite $B$ and $C$, respectively.
Suppose that the circumcenter of triangle $A_1B_1C_1$ lies
on the circumcircle of triangle $ABC$.
Prove that triangle $ABC$ is right-angled.
\item %% Problem 4
Let $ABC$ be an acute triangle with orthocenter $H$,
and let $W$ be a point on the side $\ol{BC}$, between $B$ and $C$.
The points $M$ and $N$ are the feet of the altitudes
drawn from $B$ and $C$, respectively.
Suppose $\omega_1$ is the circumcircle of triangle $BWN$
and $X$ is a point such that $\ol{WX}$ is a diameter of $\omega_1$.
Similarly, $\omega_2$ is the circumcircle of triangle $CWM$
and $Y$ is a point such that $\ol{WY}$ is a diameter of $\omega_2$.
Show that the points $X$, $Y$, and $H$ are collinear.
\item %% Problem 5
Suppose a function $f \colon \QQ_{>0} \to \RR$ satisfies:
\begin{enumerate}
\ii [(i)] If $x,y \in \QQ_{>0}$, then $f(x)f(y) \ge f(xy)$.
\ii [(ii)] If $x,y \in \QQ_{>0}$, then $f(x+y) \ge f(x) + f(y)$.
\ii [(iii)] There exists a rational number $a > 1$ with $f(a) = a$.
\end{enumerate}
Prove that $f(x) = x$ for all positive rational numbers $x$.
\item %% Problem 6
Let $n \ge 3$ be an integer,
and consider a circle with $n + 1$ equally spaced points marked on it.
Consider all labellings of these points with the numbers
$0, 1, \dots , n$ such that each label is used exactly once;
two such labellings are considered to be the same if
one can be obtained from the other by a rotation of the circle.
A labelling is called \emph{beautiful} if,
for any four labels $a < b < c < d$ with $a + d = b + c$,
the chord joining the points labelled $a$ and $d$
does not intersect the chord joining the points labelled $b$ and $c$.
Let $M$ be the number of beautiful labelings,
and let $N$ be the number of ordered pairs $(x, y)$ of positive integers
such that $x + y \le n$ and $\gcd(x, y) = 1$.
Prove that $M = N + 1$.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{IMO 2013/1, proposed by Japan}
\textsl{Available online at \url{https://aops.com/community/p5720240}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $k$ and $n$ be positive integers.
Prove that there exist positive integers $m_1$, \dots, $m_k$
such that
\[ 1 + \frac{2^k-1}{n}
= \left( 1 + \frac{1}{m_1} \right)
\left( 1 + \frac{1}{m_2} \right)
\dots
\left( 1 + \frac{1}{m_k} \right).
\]
\end{mdframed}
By induction on $k \ge 1$.
When $k = 1$ there is nothing to prove.
For the inductive step, if $n$ is even, write
\[
\frac{n + (2^k-1)}{n}
= \left( 1 + \frac{1}{n + (2^k-2)} \right)
\cdot \frac{\frac n2 + (2^{k-1}-1)}{\frac n2}
\]
and use inductive hypothesis on the second term.
On the other hand if $n$ is odd then write
\[
\frac{n + (2^k-1)}{n}
= \left( 1 + \frac{1}{n} \right)
\cdot \frac{\frac{n+1}{2} + (2^{k-1}-1)}{\frac{n+1}2}
\]
and use inductive hypothesis on the second term.
\pagebreak
\subsection{IMO 2013/2, proposed by Ivan Guo (AUS)}
\textsl{Available online at \url{https://aops.com/community/p5720110}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A configuration of $4027$ points in the plane is called
\emph{Colombian} if it consists of $2013$ red points and $2014$ blue points,
and no three of the points of the configuration are collinear.
By drawing some lines, the plane is divided into several regions.
An arrangement of lines is \emph{good} for a Colombian configuration
if the following two conditions are satisfied:
\begin{enumerate}
\ii[(i)] No line passes through any point of the configuration.
\ii[(ii)] No region contains points of both colors.
\end{enumerate}
Find the least value of $k$ such that for any Colombian configuration
of $4027$ points, there is a good arrangement of $k$ lines.
\end{mdframed}
The answer is $k \ge 2013$.
To see that $k = 2013$ is necessary,
consider a regular $4026$-gon and alternatively color the
points red and blue,
then place the last blue point anywhere
in general position (it doesn't matter).
Each side of the $4026$ is a red-blue line segment
which needs to be cut by one of the $k$ lines,
and each line can cut at most two of the segments.
Now, we prove that $k = 2013$ lines is sufficient.
Consider the convex hull of all the points.
\begin{itemize}
\ii If the convex hull has any red points,
cut that red point off from everyone else by a single line.
Then, for each of the remaining $2012$ red points,
break them into $1006$ pairs arbitrarily,
and for each pair $\{A, B\}$ draw two lines
parallel to $AB$ and close to them.
\ii If the convex hull has two consecutive blue points,
cut those two blue points off from everyone else by a single line.
Then repeat the above construction
for the remaining $2012$ blue points.
\end{itemize}
The end.
\pagebreak
\subsection{IMO 2013/3, proposed by Alexander A. Polyansky (RUS)}
\textsl{Available online at \url{https://aops.com/community/p5720184}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let the excircle of triangle $ABC$ opposite
the vertex $A$ be tangent to the side $BC$ at the point $A_1$.
Define the points $B_1$ on $CA$ and $C_1$ on $AB$ analogously,
using the excircles opposite $B$ and $C$, respectively.
Suppose that the circumcenter of triangle $A_1B_1C_1$ lies
on the circumcircle of triangle $ABC$.
Prove that triangle $ABC$ is right-angled.
\end{mdframed}
We ignore for now the given condition
and prove the following important lemma.
\begin{lemma*}
Let $(AB_1C_1)$ meet $(ABC)$ again at $X$.
From $BC_1 = B_1C$ follows $XC_1 = XB_1$,
and $X$ is the midpoint of major arc $\widehat{BC}$.
\end{lemma*}
\begin{proof}
This follows from the fact that we have
a spiral similarity $\triangle XBC_1 \sim \triangle XCB_1$
which must actually be a spiral congruence
since $BC_1 = B_1C$.
\end{proof}
We define the arc midpoints $Y$ and $Z$ similarly,
which lie on the perpendicular bisectors of
$\ol{A_1 C_1}$, $\ol{A_1 B_1}$.
\begin{center}
\begin{asy}
pair A = dir(110);
pair B = dir(180);
pair C = dir(0);
pair X = dir(90);
pair Y = dir(235);
pair Z = dir(325);
pair A_1 = foot(Y+Z-X, B, C);
pair B_1 = foot(Z+X-Y, C, A);
pair C_1 = foot(X+Y-Z, A, B);
filldraw(unitcircle, opacity(0.1)+grey, grey);
draw(C_1--X--B_1, red);
draw(A--B--C--cycle, grey);
filldraw(A_1--B_1--C_1--cycle, opacity(0.1)+cyan, heavycyan);
draw(Y--X--Z, orange);
draw(circumcircle(X, B_1, C_1), dashed+grey);
draw(X--A_1, red+dashed);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$X$", X, dir(X));
dot("$Y$", Y, dir(Y));
dot("$Z$", Z, dir(Z));
dot("$A_1$", A_1, dir(270));
dot("$B_1$", B_1, dir(B_1));
dot("$C_1$", C_1, dir(C_1));
/* TSQ Source:
A = dir 110
B = dir 180
C = dir 0
X = dir 90
Y = dir 235
Z = dir 325
A_1 = foot Y+Z-X B C R270
B_1 = foot Z+X-Y C A
C_1 = foot X+Y-Z A B
unitcircle 0.1 grey / grey
C_1--X--B_1 red
A--B--C--cycle grey
A_1--B_1--C_1--cycle 0.1 cyan / heavycyan
Y--X--Z orange
circumcircle X B_1 C_1 dashed grey
X--A_1 red dashed
*/
\end{asy}
\end{center}
We now turn to the problem condition
which asserts the circumcenter $W$ of $\triangle A_1B_1C_1$
lies on $(ABC)$.
\begin{claim*}
We may assume WLOG that $W = X$.
\end{claim*}
\begin{proof}
This is just configuration analysis,
since we already knew that the arc midpoints
both lie on $(ABC)$ and the relevant perpendicular bisectors.
Point $W$ lies on $(ABC)$ and hence outside $\triangle ABC$,
hence outside $\triangle A_1 B_1 C_1$.
Thus we may assume WLOG that $\angle B_1 A_1 C_1 > 90\dg$.
Then $A$ and $X$ lie on the same side of line $\ol{B_1 C_1}$,
and since $W$ is supposed to lie both on $(ABC)$
and the perpendicular bisector of $\ol{B_1C_1}$ it follows $W = X$.
\end{proof}
Consequently, $\ol{XY}$ and $\ol{XZ}$
are exactly the perpendicular bisectors
of $\ol{A_1 C_1}$, $\ol{A_1 B_1}$.
The rest is angle chase, the fastest one is
\begin{align*}
\angle A &= \angle C_1 X B_1
= \angle C_1 X A_1 + \angle A_1 X B_1
= 2 \angle YXA_1 + 2 \angle A_1 X Z \\
&= 2 \angle YXZ = 180\dg - \angle A
\end{align*}
which solves the problem.
\begin{remark*}
Angle chasing is also possible even without
the points $Y$ and $Z$, though it takes much longer.
Introduce the Bevan point $V$ and use the fact
that $VA_1B_1C$ is cyclic (with diameter $\ol{VC}$)
and similarly $VA_1C_1B$ is cyclic;
a calculation then gives $\angle CVB = 180\dg - \half \angle A$.
Thus $V$ lies on the circle with diameter $\ol{I_b I_c}$.
\end{remark*}
\pagebreak
\section{Solutions to Day 2}
\subsection{IMO 2013/4, proposed by Warut Suksompong, Potcharapol Suteparuk (THA)}
\textsl{Available online at \url{https://aops.com/community/p5720174}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABC$ be an acute triangle with orthocenter $H$,
and let $W$ be a point on the side $\ol{BC}$, between $B$ and $C$.
The points $M$ and $N$ are the feet of the altitudes
drawn from $B$ and $C$, respectively.
Suppose $\omega_1$ is the circumcircle of triangle $BWN$
and $X$ is a point such that $\ol{WX}$ is a diameter of $\omega_1$.
Similarly, $\omega_2$ is the circumcircle of triangle $CWM$
and $Y$ is a point such that $\ol{WY}$ is a diameter of $\omega_2$.
Show that the points $X$, $Y$, and $H$ are collinear.
\end{mdframed}
We present two solutions, an elementary one
and then an advanced one by moving points.
\paragraph{First solution, classical}
Let $P$ be the second intersection of $\omega_1$ and $\omega_2$;
this is the Miquel point, so $P$ also lies on the circumcircle of $AMN$,
which is the circle with diameter $\ol{AH}$.
\begin{center}
\begin{asy}
pair A = dir(110);
pair B = dir(210);
pair C = dir(330);
pair M = foot(B, A, C);
pair N = foot(C, A, B);
draw(B--M);
draw(C--N);
filldraw(A--B--C--cycle, opacity(0.1)+lightcyan, lightblue);
draw(B--M, lightblue);
draw(C--N, lightblue);
pair W = 0.55*C+0.45*B;
pair H = A+B+C;
pair P = foot(H, A, W);
pair X = extension(P, H, B, B+A-H);
pair Y = extension(P, H, C, C+A-H);
filldraw(circumcircle(B, N, W), opacity(0.1)+lightgreen, heavygreen);
filldraw(circumcircle(C, M, W), opacity(0.1)+lightgreen, heavygreen);
draw(X--W--Y, heavygreen);
draw(B--X, lightblue);
draw(C--Y, lightblue);
draw(X--Y, red+dotted);
draw(A--W, red+dotted);
draw(circumcircle(A, M, N), red+dashed);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$M$", M, dir(M));
dot("$N$", N, dir(N));
dot("$W$", W, dir(W));
dot("$H$", H, dir(H));
dot("$P$", P, dir(P));
dot("$X$", X, dir(X));
dot("$Y$", Y, dir(Y));
/* TSQ Source:
A = dir 110
B = dir 210
C = dir 330
M = foot B A C
N = foot C A B
B--M
C--N
A--B--C--cycle 0.1 lightcyan / lightblue
B--M lightblue
C--N lightblue
W = 0.55*C+0.45*B
H = A+B+C
P = foot H A W
X = extension P H B B+A-H
Y = extension P H C C+A-H
circumcircle B N W 0.1 lightgreen / heavygreen
circumcircle C M W 0.1 lightgreen / heavygreen
X--W--Y heavygreen
B--X lightblue
C--Y lightblue
X--Y red dotted
A--W red dotted
circumcircle A M N red dashed
*/
\end{asy}
\end{center}
We now contend:
\begin{claim*}
Points $P$, $H$, $X$ collinear.
(Similarly, points $P$, $H$, $Y$ are collinear.)
\end{claim*}
\begin{proof}
[Proof using power of a point]
By radical axis on $BNMC$, $\omega_1$, $\omega_2$,
it follows that $A$, $P$, $W$ are collinear.
We know that $\angle APH = 90\dg$, and also
$\angle XPW = 90\dg$ by construction.
Thus $P$, $H$, $X$ are collinear.
\end{proof}
\begin{proof}
[Proof using angle chasing]
This is essentially Reim's theorem:
\[ \dang NPH = \dang NAH = \dang BAH = \dang ABX = \dang NBX = \dang NPX \]
as desired.
Alternatively, one may prove $A$, $P$, $W$ are collinear by
$\dang NPA = \dang NMA = \dang NMC = \dang NBC = \dang NBW = \dang NPW$.
\end{proof}
\paragraph{Second solution, by moving points}
Fix $\triangle ABC$ and vary $W$.
Let $\infty$ be the point at infinity perpendicular to $\ol{BC}$
for brevity.
By spiral similarity, the point $X$ moves linearly on $\ol{B\infty}$
as $W$ varies linearly on $\ol{BC}$.
Similarly, so does $Y$.
So in other words, the map \[ X \mapsto W \mapsto Y \]
is linear.
However, the map \[ X \mapsto Y' \coloneqq \ol{XH} \cap \ol{C\infty} \]
is linear too.
To show that these maps are the same,
it suffices to check it thus at two points.
\begin{itemize}
\ii When $W = B$, the circle $(BNW)$
degenerates to the circle through $B$ tangent to $\ol{BC}$,
and $X = \ol{CN} \cap \ol{B\infty}$.
We have $Y = Y' = C$.
\ii When $W = C$, the result is analogous.
\ii Although we don't need to do so,
it's also easy to check the result if $W$
is the foot from $A$
since then $XHWB$ and $YHWC$ are rectangles.
\end{itemize}
\pagebreak
\subsection{IMO 2013/5, proposed by Bulgaria}
\textsl{Available online at \url{https://aops.com/community/p5720286}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Suppose a function $f \colon \QQ_{>0} \to \RR$ satisfies:
\begin{enumerate}
\ii [(i)] If $x,y \in \QQ_{>0}$, then $f(x)f(y) \ge f(xy)$.
\ii [(ii)] If $x,y \in \QQ_{>0}$, then $f(x+y) \ge f(x) + f(y)$.
\ii [(iii)] There exists a rational number $a > 1$ with $f(a) = a$.
\end{enumerate}
Prove that $f(x) = x$ for all positive rational numbers $x$.
\end{mdframed}
First, we dispense of negative situations by proving:
\begin{claim*}
For any integer $n > 0$, we have $f(n) \ge n$.
\end{claim*}
\begin{proof}
Note by induction on (ii) we have $f(nx) \ge n f(x)$.
Taking $(x,y) = (a,1)$ in (i) gives $f(1) \ge 1$,
and hence $f(n) \ge n$.
\end{proof}
\begin{claim*}
The $f$ takes only positive values,
and hence by (ii) is strictly increasing.
\end{claim*}
\begin{proof}[Proof, suggested by Gopal Goel]
Let $p,q > 0$ be integers.
Then $f(q) f(p/q) \ge f(p)$,
and since both $\min(f(p), f(q)) > 0$
it follows $f(p/q) > 0$.
\end{proof}
\begin{claim*}
For any $x > 1$ we have $f(x) \ge x$.
\end{claim*}
\begin{proof}
Note that
\[ f(x)^N \ge f(x^N) \ge f\left( \left\lfloor x^N \right\rfloor \right)
\ge \left\lfloor x^N \right\rfloor > x^N-1 \]
for any integer $N$.
Since $N$ can be arbitrarily large,
we conclude $f(x) \ge x$ for $x > 1$.
\end{proof}
On the other hand, $f$ has arbitrarily large fixed points
(namely powers of $a$) so from (ii) we're essentially done.
First, for $x > 1$ pick a large $m$ and note
\[ a^m = f(a^m) \ge f(a^m-x) + f(x) \ge (a^m-x)+x = a^m. \]
Finally, for $x \le 1$ use
\[ nf(x) = f(n)f(x) \ge f(nx) \ge nf(x) \]
for large $n$.
\begin{remark*}
Note that $a > 1$ is essential;
if $b \ge 1$ then $f(x) = bx^2$ works with unique fixed point $1/b \le 1$.
\end{remark*}
\pagebreak
\subsection{IMO 2013/6, proposed by Russia}
\textsl{Available online at \url{https://aops.com/community/p5720264}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n \ge 3$ be an integer,
and consider a circle with $n + 1$ equally spaced points marked on it.
Consider all labellings of these points with the numbers
$0, 1, \dots , n$ such that each label is used exactly once;
two such labellings are considered to be the same if
one can be obtained from the other by a rotation of the circle.
A labelling is called \emph{beautiful} if,
for any four labels $a < b < c < d$ with $a + d = b + c$,
the chord joining the points labelled $a$ and $d$
does not intersect the chord joining the points labelled $b$ and $c$.
Let $M$ be the number of beautiful labelings,
and let $N$ be the number of ordered pairs $(x, y)$ of positive integers
such that $x + y \le n$ and $\gcd(x, y) = 1$.
Prove that $M = N + 1$.
\end{mdframed}
First, here are half of the beautiful labellings up to reflection for $n = 6$,
just for concreteness.
\begin{center}
\begin{asy}
size(9cm);
pair g(int n) { return dir(90 + 60*n); }
picture ring(int a, int b, int c, int d, int e, real r) {
picture pic = new picture;
draw(pic, unitcircle);
draw(pic, dir(90)--dir(r), dotted+blue);
draw(pic, g(a)--g(e), dotted+blue);
draw(pic, g(b)--g(d), dotted+blue);
dot(pic, "$0$", dir(90), dir(90));
dot(pic, "$1$", g(a), g(a));
dot(pic, "$2$", g(b), g(b));
dot(pic, "$3$", g(c), g(c));
dot(pic, "$4$", g(d), g(d));
dot(pic, "$5$", g(e), g(e));
dot(pic, "$6$", dir(r), dir(r), red);
return pic;
}
add(shift(3,6)*ring(2,4,5,1,3,0));
add(shift(0,6)*ring(3,1,4,2,5,240));
add(shift(3,3)*ring(4,2,5,3,1,0));
add(shift(0,3)*ring(2,3,4,5,1,240));
add(shift(3,0)*ring(1,2,3,4,5,50));
add(shift(0,0)*ring(1,2,3,4,5,130));
\end{asy}
\end{center}
Abbreviate ``beautiful labelling of points around a circle'' to ring.
Moreover, throughout the solution we will allow degenerate
chords that join a point to itself;
this has no effect on the problem statement.
The idea is to proceed by induction in the following way.
A ring of $[0,n]$ is called \emph{linear}
if it is an arithmetic progression modulo $n+1$.
For example, the first two rings in the diagram
and the last one are linear for $n = 6$,
while the other three are not.
Of course we can move from any ring on $[0,n]$
to a ring on $[0,n-1]$ by deleting $n$.
We are going to prove that:
\begin{itemize}
\ii Each linear ring on $[0,n-1]$ yields exactly two
rings of $[0,n]$, and
\ii Each nonlinear ring on $[0,n-1]$ yields exactly one
rings of $[0,n]$.
\end{itemize}
In light of the fact there are obviously $\varphi(n)$ linear rings on $[0,n]$,
the conclusion will follow by induction.
We say a set of chords (possibly degenerate) is \emph{pseudo-parallel}
if for any three of them, one of them separates the two.
(Pictorially, one can perturb the endpoints along the circle
in order to make them parallel in Euclidean sense.)
The main structure lemma is going to be:
\begin{lemma*}
In any ring, the chords of sum $k$
(even including degenerate ones) are pseudo-parallel.
\end{lemma*}
\begin{proof}
By induction on $n$.
By shifting, we may assume that one of the chords is $\{0,k\}$
and discard all numbers exceeding $k$; that is, assume $n = k$.
Suppose the other two chords are $\{a, n-a\}$ and $\{b, n-b\}$.
\begin{center}
\begin{asy}
size(5cm);
draw(unitcircle);
pair O = dir(210);
pair N = dir(330);
draw(O--N);
pair A1 = dir(100);
pair A2 = dir(140);
pair B1 = dir( 80);
pair B2 = dir( 40);
draw(A1--A2);
draw(B1--B2);
pair U = dir(200);
pair V = dir(340);
draw(U--V, blue);
pair X = dir(250);
pair Y = dir(310);
draw(X--Y, red);
draw(O--X, blue+dashed);
dot("$a$", A1, A1);
dot("$b$", B1, B1);
dot("$n-a$", A2, A2);
dot("$n-b$", B2, B2);
dot("$u$", U, U, blue);
dot("$v$", V, V, blue);
dot("$u+v$", X, X, red);
dot("$n-(u+v)$", Y, Y, red);
dot("$0$", O, O);
dot("$n$", N, N);
\end{asy}
\end{center}
We consider the chord $\{u,v\}$ directly above $\{0,n\}$, drawn in blue.
There are now three cases.
\begin{itemize}
\ii If $u+v = n$, then delete $0$ and $n$
and decrease everything by $1$.
Then the chords $\{a-1, n-a-1\}$, $\{b-1, n-b-1\}$, $\{u-1, v-1\}$
contradict the induction hypothesis.
\ii If $u+v < n$, then search for the chord
$\{u+v, n-(u+v)\}$.
It lies on the other side of $\{0, n\}$
in light of chord $\{0,u+v\}$.
Now again delete $0$ and $n$ and decrease everything by $1$.
Then the chords $\{a-1, n-a-1\}$, $\{b-1, n-b-1\}$, $\{u-1, v-1\}$
contradict the induction hypothesis.
%% MAX LU: this case can't occur at all;
%% nowhere to put $n-u$ without $0+n = u+(n-u)
%% and $v + (n-(u+v))$.
\ii If $u+v > n$, apply the map $t \mapsto n-t$ to the entire ring.
This gives the previous case as now $(n-u)+(n-v) < n$.
\qedhere
\end{itemize}
\end{proof}
Next, we give another characterization of linear rings.
\begin{lemma*}
A ring on $[0,n-1]$ is linear if and only if the point $0$
does not lie between two chords of sum $n$.
\end{lemma*}
\begin{proof}
It's obviously true for linear rings.
Conversely, assume the property holds for some ring.
Note that the chords with sum $n-1$ are pseudo-parallel and encompass every point,
so they are \emph{actually} parallel.
Similarly, the chords of sum $n$ are \emph{actually} parallel
and encompass every point other than $0$.
So the map
\[ t \mapsto n-t \mapsto (n-1)-(n-t) = t-1 \pmod n \]
is rotation as desired.
\end{proof}
\begin{lemma*}
Every nonlinear ring on $[0,n-1]$ induces exactly one ring on $[0,n]$.
\end{lemma*}
\begin{proof}
Because the chords of sum $n$ are pseudo-parallel,
there is at most one possibility for the location $n$.
Conversely, we claim that this works.
The chords of sum $n$ (and less than $n$) are OK by construction, so
assume for contradiction that there exists $a,b,c \in \{1,\dots,n-1\}$
such that $a + b = n + c$.
Then, we can ``reflect'' them using the (pseudo-parallel)
chords of length $n$ to find that $(n-a) + (n-b) = 0 + (n-c)$,
and the chords joining $0$ to $n-c$ and $n-a$ to $n-b$ intersect,
by definition.
\begin{center}
\begin{asy}
size(5cm);
draw(unitcircle);
draw(dir(140)--dir(220), blue+dotted);
draw(dir(250)--dir(110), blue+dotted);
draw(dir(340)--dir(20), blue+dotted);
draw(dir(60)--dir(300), blue+dotted);
draw(dir(220)--dir(60), lightred);
draw(dir(340)--dir(110), lightred);
draw(dir(140)--dir(300), orange+dashed);
draw(dir(250)--dir(20), orange+dashed);
dot("$0$", dir(140), dir(140));
dot("$n$", dir(220), dir(220), red);
dot("$n-a$", dir(250), dir(250));
dot("$n-c$", dir(300), dir(300));
dot("$b$", dir(340), dir(340));
dot("$n-b$", dir(20), dir(20));
dot("$c$", dir(60), dir(60));
dot("$a$", dir(110), dir(110));
\end{asy}
\end{center}
This is a contradiction that the original numbers on $[0,n-1]$ form a ring.
\end{proof}
\begin{lemma*}
Every linear ring on $[0,n-1]$ induces
exactly two rings on $[0,n]$.
\end{lemma*}
\begin{proof}
Because the chords of sum $n$ are pseudo-parallel,
the point $n$ must lie either directly to the left or right of $0$.
For the same reason as in the previous proof, both of them work.
\end{proof}
\pagebreak
\end{document}