\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{ToT Spring 2011 S-A7}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 72}
\maketitle
\section*{Problem}
Suppose $100$ red points divide a blue circle into $100$ arcs
such that their lengths are all positive integers from $1$ to $100$
in an arbitrary order.
Prove that there exist two perpendicular chords with red endpoints.
\section*{Video}
\href{https://www.youtube.com/watch?v=DgsH-Nn2fOo&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/DgsH-Nn2fOo}}
\newpage
\section*{Solution}
We will assume no two red points are diametrically opposite,
otherwise, the problem is trivial.
\begin{claim*}
If there exist two intervals which have sum of lengths $2525$,
and it is not the case that
\begin{itemize}
\ii the intervals share an endpoint; and
\ii one interval contains the other
\end{itemize}
then the problem is solved.
\end{claim*}
\begin{proof}
Since no diametrically opposite points,
it follows that we only need concern the case
where the intervals do not share an endpoint.
In that case, consider the points which lie in
exactly one of the two intervals.
They form arcs with sum of length $2525$, solving problem.
\end{proof}
For every red point $R$,
we define its two \emph{attached arcs} to be the
two maximal-by-inclusion arcs with endpoint $R$ and total
length at most $2525$.
See figure below with two attached arcs drawn.
\begin{center}
\begin{asy}
dotfactor *= 2;
size(6cm);
draw(unitcircle);
dot("$R$", dir(180), dir(45), red);
label("$-R$", dir(0), dir(0));
dot(dir(0), grey);
draw(arc(origin, dir(20)*1.1, dir(180)*1.1), deepgreen+1.4);
draw(arc(origin, dir(180)*0.9, dir(330)*0.9), deepcyan+1.4);
dot(dir(20), red);
dot(dir(330), red);
\end{asy}
\end{center}
Then, of these two, we pick the one with longest length
and call it the \emph{main arc} of $R$.
A main arc $\Gamma$
always has length $2525-x$ for some $0 < x \le 50$.
We refer to the given arc of length $x$
as the \emph{killer} of $\Gamma$.
Now, the problem is solved unless we are in a situation
where for every main arc $\Gamma$,
its killer is contained $\Gamma$ and shares an endpoint with it.
\begin{claim*}
If there exists any main arc with $x=50$, we are done.
\end{claim*}
\begin{proof}
It means the two attached arcs both have length exactly $2475$,
and that the segment of length $100$ is split exactly
by the antipode of $R$.
So the segment of length $50$ can't be killers of both.
\end{proof}
\begin{claim*}
If any arc of length $x < 50$ is the killer of two different
main arcs, we are done.
\end{claim*}
\begin{proof}
If it was the killer of two attached arcs,
then we have the following picture.
\begin{center}
\begin{asy}
size(6cm);
draw(unitcircle);
draw(arc(origin, dir(80), dir(100)), red+1.8);
draw(arc(origin, dir(80)*1.1, dir(240)*1.1), deepgreen+1.4);
draw(arc(origin, dir(-60)*0.9, dir(100)*0.9), deepcyan+1.4);
draw(arc(origin, dir(240), dir(300)), grey+1.8);
label("$x$", dir(90)*0.9, dir(-90), red);
label("$2525-x$", dir(160)*1.1, dir(160), deepgreen);
label("$2525-x$", dir(20)*0.9, -dir(20), deepgreen);
label("$3x$", dir(270)*1.1, grey);
dotfactor *= 2;
dot(dir(80), red);
dot(dir(100), red);
dot(dir(240), red);
dot(dir(300), red);
label("$B$", dir(80), dir(45), red);
label("$A$", dir(100), dir(225), red);
label("$C$", dir(240), -dir(240), red);
label("$D$", dir(300), dir(310), red);
\end{asy}
\end{center}
Since $2x < 100$, we can consider the
arc of length $2x$.
Both arcs $AC$ and $BD$ have length $2525-2x$.
The arc of length $2x$ can't share an endpoint with both at once.
\end{proof}
Finally, note that there are at least $50$ main arcs
(each choice of $R$ generates one,
and each main arc appears at most twice this way),
but only $49$ possible killers.
So this solves the problem.
\end{document}