\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$ with odd multiplicity.
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}