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

\begin{document}
\title{Mexico 2020/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 55}
\maketitle

\section*{Problem}
Let $n\ge 3$ be an integer.
Two players, Ana and Beto, play the following game.
Ana tags the vertices of a regular $n$-gon with the numbers from $1$ to $n$,
in any order she wants.
Every vertex must be tagged with a different number.
Then, we place a turkey in each of the $n$ vertices.

These turkeys are trained for the following.
If Beto whistles, each turkey moves to the adjacent vertex with greater tag.
If Beto claps, each turkey moves to the adjacent vertex with lower tag.
Beto wins if, after some number of whistles and claps,
he gets to move all the turkeys to the same vertex.
Ana wins if she can tag the vertices so that Beto can't do this.
For each $n\ge 3$, determine which player has a winning strategy.

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

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

\newpage

\section*{Solution}
The answer is that Beto wins if $n$ is an odd prime,
and otherwise Ana wins.

If $n$ is even, Ana wins no matter what the tagging is,
because by coloring the vertices of the $n$-gon in alternating colors,
we find that the number of turkeys on one color
always equals the number of turkeys of the other color.
Therefore, we will assume $n$ is odd in what follows.

\begin{claim*}
  For Beto to win,
  it is necessary and sufficient for Beto
  to be able to merge any two given turkeys.
\end{claim*}
\begin{proof}
  Clear.
\end{proof}

Given two turkeys with odd $n$,
there is a notion of \emph{even distance} $d$ between them
(by drawing the arc of even length).
Hence one of \emph{left} or \emph{right} turkey.
Note that:
\begin{itemize}
  \ii There is always a choice of move that moves
  the right turkey counterclockwise;
  hence it cannot decrease the even distance.
  We call this a \emph{safe move}.

  \ii Beto could try to decrease the even distance
  by repeatedly applying safe moves.
  If at any point one of the safe moves causes
  the left turkey to move clockwise (rather than counterclockwise),
  the even distance will decrease.
  If he is always able to do this, for any $d > 0$,
  he can eventually merge the turkeys.

  \ii On the other hand, suppose there is an even distance $d$
  for which safe moves do not ever decrease the distance.
  Then both turkeys will traverse the entire circle.
\end{itemize}

With that notation, let's work through both situations.
In what follows, the vertices are labeled $A_0$, $A_1$, \dots, $A_{n-1}$
in counterclockwise order, indices modulo $n$.

\paragraph{Proof that Beto wins whenever $n$ is prime.}
Suppose for contradiction that there is an even distance $d$
such that Beto cannot get two turkeys of even distance $d$ closer.

Consider any two vertices, say $A_0$ and $A_d$ which are $d$ apart.
WLOG, suppose that clapping is a safe move
(in other words, $A_{n-1} > A_1$).
Then the clap makes the other turkey move away,
meaning that $A_{d-1} > A_{d+1}$.
This situation is illustrated for $d=4$ below,
with green arrows marking the clap direction.
\begin{center}
\begin{asy}
  picture turkey;
  pen turkeyborder = black+1.2;
  pair[] A = new pair[11];
  for (int i=0; i<=10; ++i) {
    A[i] = 5*dir(360*i/11);
  }

  picture leg;
  pen turkeyleg = rgb("cc3300") + 1.2;
  filldraw(turkey, scale(0.7)*unitcircle, rgb("cc0000"), turkeyborder);
  draw(leg, (0.5*dir(-70))--(1.6*dir(-70)), turkeyleg);
  draw(leg, (1.3*dir(-70))--(1.3*dir(-70)+0.3*dir(-95)), turkeyleg);
  draw(leg, (1.3*dir(-70))--(1.3*dir(-70)+0.3*dir(-50)), turkeyleg);
  add(turkey, leg);
  add(turkey, reflect(dir(-90), dir(90))*leg);
  filldraw(turkey, (1,0)--(-1,0)..(0,-1)..cycle, rgb("604020"), turkeyborder); // body of turkey
  draw(turkey, (0.1,-0.4)..(-0.2,-0.35)..(-0.6,-0.2), turkeyborder); // part of wing
  draw(turkey, (0.1,-0.8)..(-0.2,-0.7)..(-0.6,-0.2), turkeyborder); // part of wing
  filldraw(turkey, (1.2,0.3)--(1.2,0)--(1.7,0.15)--cycle, yellow, turkeyborder); // beak of turkey
  filldraw(turkey, circle((0.7,0.3), 0.6), rgb("e67300"), turkeyborder); // turkey head
  fill(turkey, ellipse((1.05,0.45), 0.08, 0.12), black);
  fill(turkey, ellipse((1.07,0.49), 0.02, 0.03), white);
  draw(turkey, (1.6,0.5)--(1.8,0.7)..(2.0,0.75)..(2.4,1.2)..(1.8,1.5)..(1.2,1.2)..(1.6,0.7)--cycle );
  label(turkey, scale(0.7)*"\textsf{gobble}", (1.8,1.1), fontsize(9pt));
  add(shift(1.4*A[0])*rotate(-90)*turkey);
  add(shift(1.4*A[4])*rotate(40)*turkey);

  size(9cm);
  draw(scale(5)*unitcircle, grey);
  dotfactor *= 2;
  draw(A[0]--A[4], blue);
  draw(A[4]--A[8], lightblue+dashed);
  draw(arc(origin, A[0], A[1]), deepgreen+1.8, EndArrow(TeXHead), Margin(0,4));
  draw(arc(origin, A[4], A[5]), deepgreen+1.8, EndArrow(TeXHead), Margin(0,4));
  draw(arc(origin, A[8], A[9]), deepgreen+1.8, EndArrow(TeXHead), Margin(0,4));
  draw(A[10]--A[1], red, EndArrow(TeXHead), Margins);
  draw(A[3]--A[5], red, EndArrow(TeXHead), Margins);
  label(rotate(90)*"bigger than", A[10]--A[1], dir(180), red);

  for (int i=0; i<=10; ++i) {
    dot(A[i]);
  }
\end{asy}
\end{center}
Now imagine the turkeys are situated at $A_d$ and $A_{2d}$.
We have seen that clapping is the safe move for $A_d$;
hence clapping is the safe move for $A_{2d}$ as well.

Repeating this argument, and noting that $d < n$ means $\gcd(d,n) = 1$,
we find that clapping is the safe move at \emph{every} vertex.
And that means we have the inequality chain
\[ A_{n-1} > A_1 > A_3 > A_5 > \dots \]
but this chain is cyclic and we get a contradiction.

\paragraph{Proof that Beto loses whenever $n$ is composite.}
On the other hand if $n$ is an odd composite number,
let $p$ be the smallest prime divisor of $n$,
and focus on $d = 2 \cdot \frac np$.

Then label $A_1$, $A_3$, \dots, $A_{n-2}$, $A_n$, $A_2$, \dots, $A_{n-1}$
as the following numbers, in order:
\begin{itemize}
  \ii $1$, $p+1$, $2p+1$, \dots, $n-p+1$
  \ii $2$, $p+2$, $2p+2$, \dots, $n-p+2$
  \ii \dots
  \ii $p$, $2p$, $3p$, \dots, $n$.
\end{itemize}
Then, every $\frac np$'th vertex will have safe move ``whistle'',
and the rest will have safe move ``clap''.
This completes the solution.

\end{document}
