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

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

\section*{Problem}
Megumin is given $6$ numbers $1, 2, 3, 4, 5, 6$ in the whiteboard.
Every turn, she can choose 2 distinct numbers $x \neq y$ and replace
them with the two numbers
\[ \frac{xy}{|x - y|} \quad \text{and} \quad \frac{\max \{ x ,y \} }{2}. \]
Determine the minimum possible number that could appear in the whiteboard.

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



\newpage

\section*{Solution}
Rather than working with number $x$ itself,
we instead work with the number $\frac{60}{x}$.
Hence we may think of operation as
\begin{itemize}
  \ii Start with $60$, $30$, $20$, $15$, $12$, $10$.
  \ii Replace $a$, $b$ with $\left\lvert a-b \right\rvert$ and $2\min\{a,b\}$.
  \ii Try to maximize the number on board.
\end{itemize}

\begin{claim*}
  The sum of numbers on board is constant.
\end{claim*}
\begin{proof}
  Clear.
\end{proof}
\begin{claim*}
  The numbers on the board are always positive integers.
\end{claim*}
\begin{proof}
  Clear.
\end{proof}

\begin{claim*}
  There is at most one odd integer on the board at all times.
\end{claim*}
\begin{proof}
  This is true at the start,
  and the operation preserves this
  (it is impossible to get more odd integers
  than one started with in the operation).
\end{proof}

The sum of the numbers on the board is initially
$10+12+15+20+30+60 = 147$,
so we cannot get a number larger than $147 - (1+2+2+2+2) = 138$.

This turns out to be actually achievable though:
the following ad-hoc construction achieves it.
In each step we repeatedly operate on two numbers to change the values.
\begin{itemize}
  \ii 10 12 15 20 30 60
  \ii 2 20 15 20 30 60
  \ii 4 18 15 20 30 60
  \ii 8 18 15 16 30 60
  \ii 16 18 15 16 22 60
  \ii 32 18 15 16 22 44
\end{itemize}
Re-order the values for legibility and continue:
\begin{itemize}
  \ii 15 16 18 22 32 44
  \ii 2 29 18 22 32 44
  \ii 2 2 45 22 32 44
  \ii 2 2 2 22 75 44
  \ii 2 2 2 2 95 44
  \ii 2 2 2 2 2 137
  \ii 1 2 2 2 2 138
\end{itemize}
So the maximum $138$ can indeed be reached.

Hence the answer to the original problem is $\frac{60}{138} = \frac{10}{23}$.

\end{document}
