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

\begin{document}
\title{Twitch 119.2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 119}
\maketitle

\section*{Problem}
Let $n$ be a positive integer.
There are $2n$ kids in a circle each given $2$ cards,
where the $4n$ cards are numbered uniquely from $1$ to $4n$.
Every second, each child instantaneously passes their larger-valued card
to the child on their right and their smaller-valued card to the child on the left.
The game ends when a child has two cards of consecutive value.
Show that if the game does not end within the first $n-1$ seconds,
then the game will never end.

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



\newpage

\section*{Solution}
Change the rules such that a child keeps their largest card
and passes the smaller card two kids to their left.
Hence the largest cards stay in place.
Moreover, only kids of the same parity around the circle ever interact,
so we may restrict attention to
the $n$ even-numbered kids, say.
Let $C_1 < C_2 < \dots < C_{2n}$ denote their $2n$ cards in order.

We color the cards $C_{n}$, $C_{n+1}$, \dots, $C_{2n}$ \emph{green}.
The green cards have the property that:
\begin{itemize}
  \ii A child with two green cards will pass one of them;
  \ii A child with one green cards passes the non-green one;
  \ii A child with no green cards passes either one.
\end{itemize}
We are going to use the following lemma now:
\begin{lemma*}
  [Raney]
  In a sequence of integers $(x_1, \dots, x_n)$ with sum $1$,
  there exists a unique cyclic shift with
  all partial sums strictly positive.
\end{lemma*}
Apply the lemma to the sequence of integers which is $\{-1,0,1\}$ at a kid
according to whether they have zero, one, or two green cards to start.
Then label the kids around the circle $K_1$, $K_2$, \dots, $K_n$
according to the unique cyclic shift given by the lemma.

\begin{claim*}
  We have:
  \begin{itemize}
    \ii At the end of the process,
    the cards $C_{n+1}$, \dots, $C_{2n}$ are held by different kids.
    \ii Right after the $(n-1)$st second,
    $C_n$ and $C_{n+1}$ are held by kid $K_n$.
  \end{itemize}
\end{claim*}
\begin{proof}
  To be written later (it does not require any idea and sort of follows
  by the construction, but it requires a lot of words to explain well).
\end{proof}

So there are two cases:
\begin{itemize}
  \ii If $C_n$ and $C_{n+1}$ had non-consecutive numbers,
  then no kid will ever hold cards of consecutive numbers again
  (since they always have one card at least $C_{n+1}$
  and one card at most $C_n$).

  \ii If $C_n$ and $C_{n+1}$ are consecutive
  the game ended already after at most $n-1$ seconds.
\end{itemize}

\end{document}
