\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{TSTST 2013/9}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 41}
\maketitle

\section*{Problem}
Let $r$ be a rational number in the interval $[-1,1]$
and let $\theta = \cos^{-1} r$.
Call a subset $S$ of the plane good if $S$ is unchanged
upon rotation by $\theta$ around any point of $S$
(in both clockwise and counterclockwise directions).
Determine all values of $r$ satisfying the following property:
The midpoint of any two points in a good set also lies in the set.

\section*{Video}
\href{https://www.youtube.com/watch?v=NQe9616AqXU&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/NQe9616AqXU}}

\section*{External Link}
\url{https://aops.com/community/p3181487}

\newpage

\section*{Solution}
The answer is that $r$ has this property
if and only if $r = \frac{4n-1}{4n}$ for some integer $n$.

Throughout the solution, we will let $r = \frac ab$ with $b > 0$ and
$\gcd(a,b) = 1$. We also let
\[ \omega = e^{i\theta} = \frac ab \pm \frac{\sqrt{b^2-a^2}}{b} i. \]
This means we may work with complex multiplication in the usual way;
the rotation of $z$ through center $c$ is given by $z \mapsto \omega(z-c)+c$.

For most of our proof, we start by constructing a good set as follows.
\begin{itemize}
  \ii Start by letting $S_0 = \{0, 1\}$.
  \ii Let $S_i$ consist of $S_{i-1}$ plus
  all points that can be obtained by rotating a point of $S_{i-1}$
  through a different point of $S_{i-1}$ (with scale factor $\omega$).
  \ii Let $S_\infty = \bigcup_{i \ge 0} S_i$.
\end{itemize}
The set $S_\infty$ is the (minimal, by inclusion) good set containing
$0$ and $1$.
We are going to show that for most values of $r$,
we have $\half \notin S_\infty$.

\begin{claim*}
  If $b$ is odd, then $\half \notin S_\infty$.
\end{claim*}
\begin{proof}
  Idea: denominators that appear are always odd.

  Consider the ring
  \[ A = \ZZ_{\{b\}} = \left\{ \frac{s}{t} \mid s,t \in \ZZ, t \mid b^\infty \right\} \]
  which consists of all rational numbers
  whose denominators divide $b^\infty$.
  Then, $0, 1, \omega \in A[\sqrt{b^2-a^2}]$
  and hence $S_\infty \subseteq A[\sqrt{b^2-a^2}]$ too.
  (This works even if $\sqrt{b^2-a^2} \in \ZZ$,
  in which case $S_\infty \subseteq A = A[\sqrt{b^2-a^2}]$.)

  But $\half \notin A[\sqrt{b^2-a^2}]$.
\end{proof}

\begin{claim*}
  If $b$ is even and $|b-a| \neq 1$, then $\half \notin S_\infty$.
\end{claim*}
\begin{proof}
  Idea: take modulo a prime dividing $b-a$.

  Let $D = b^2-a^2 \equiv 3 \pmod 4$.
  Let $p$ be a prime divisor of $b-a$.
  Because $\gcd(a,b) = 1$, we have $p \neq 2$ and $p \nmid b$.

  Consider the ring
  \[ A = \ZZ_{(p)} = \left\{ \frac{s}{t} \mid s,t \in \ZZ, p \perp t \right\} \]
  which consists of all rational numbers whose denominators are coprime to $p$.
  Then, $0, 1, \omega \in A[\sqrt{-D}]$ and hence $S_\infty \subseteq A[\sqrt{-D}]$ too.

  Now, there is a well-defined ``mod-$p$'' ring homomorphism
  \[ \Psi \colon A[\sqrt{-D}] \to \FF_p \quad\text{by}\quad
    x+y\sqrt{-D} \mapsto x \bmod p \]
  which commutes with addition and multiplication (as $p \mid D$).
  Under this map,
  \[ \omega \mapsto \frac ab \bmod p = 1. \]
  Consequently, the rotation $z \mapsto \omega(z-c)+c$
  is just the identity map modulo $p$.
  In other words, the pre-image of any point in $S_\infty$
  under $\Psi$ must be either $\Psi(0) = 0$ or $\Psi(1) = 1$.

  However, $\Psi(1/2) = 1/2$ is neither of these. So this point cannot be achieved.
\end{proof}

\begin{claim*}
  Suppose $a = 2n-1$ and $b=2n$ for $n$ an odd integer.
  Then $\half \notin S_\infty$
\end{claim*}
\begin{proof}
  Idea: $\omega$ is ``algebraic integer'' sans odd denominators.

  This time, we define the ring
  \[ B = \ZZ_{(2)} = \left\{ \frac{s}{t} \mid s,t \in \ZZ, t \text{ odd} \right\} \]
  of rational numbers with odd denominator.
  We carefully consider the ring $B[\omega]$ where
  \[ \omega = \frac{2n-1 \pm \sqrt{1-4n}}{2n}. \]
  So $S_\infty \subseteq B[\omega]$ as $0, 1, \omega \in B[\omega]$.

  I claim that $B[\omega]$ is an integral extension of $B$;
  equivalently that $\omega$ is integral over $B$.
  Indeed, $\omega$ is the root of the monic polynomial
  \[  (T-1)^2 + \frac1n (T-1) - \frac 1n = 0 \]
  where $\frac1n \in B$ makes sense as $n$ is odd.

  On the other hand, $\half$ is not integral over $B$
  so it is not an element of $B[\omega]$.
\end{proof}

It remains to show that if $r = \frac{4n-1}{4n}$, then goods sets
satisfy the midpoint property.
Again starting from the points $z_0 = 0$, $z_1 = 1$ construct the sequence
\begin{align*}
  z_2 &= \omega(z_1-z_0) + z_0 \\
  z_3 &= \omega\inv(z_0-z_2) + z_2 \\
  z_4 &= \omega\inv(z_2-z_3) + z_3 \\
  z_5 &= \omega(z_3-z_4) + z_4
\end{align*}
as shown in the diagram below.
\begin{center}
\begin{asy}
  size(8cm);
  pair z0 = (0,0);
  pair z1 = (1,0);
  real theta = 28.96;
  pair z2 = rotate(theta, z0) * z1;
  pair z3 = rotate(-theta, z2) * z0;
  pair z4 = rotate(-theta, z3) * z2;
  pair z5 = rotate(theta, z4) * z3;
  draw(arc(z0, z1, z2), lightgreen);
  draw(arc(z3, z4, z2), lightgreen);
  draw(arc(z2, z3, z0), lightgreen);
  draw(arc(z4, z3, z5), lightgreen);
  draw(z1--z0--z2--z3--z4--z5, deepcyan);
  dot("$z_0=0$", z0, dir(-45), red);
  dot("$z_1=1$", z1, dir(-45), red);
  dot("$z_2$", z2, dir(90));
  dot("$z_3$", z3, dir(90));
  dot("$z_4=2r-1$", z4, dir(-90));
  dot("$z_5=2r-2$", z5, dir(-90));
\end{asy}
\end{center}
This construction shows that if we have the length-one segment
$\{0,1\}$ then we can construct the length-one segment $\{2r-2, 2r-1\}$.
In other words, we can shift the segment to the left by
\[ 1-(2r-1) = 2(1-r) = \frac{1}{2n}. \]
Repeating this construction $n$ times gives the desired midpoint $\half$.

\end{document}
