\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{SJMO 2020/2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 26}
\maketitle
\section*{Problem}
Anthony writes the $(n+1)^2$ distinct positive integer divisors of $10^n$,
each once, on a whiteboard.
On a move, he may choose any two distinct numbers $a$ and $b$ on the board,
erase them both, and write $\gcd(a, b)$ twice.
Anthony keeps making moves until all of the numbers
on the board are the same.
Find the minimum possible number of moves Anthony could have made.
\section*{Video}
\href{https://www.youtube.com/watch?v=uLAvYA0CpSo&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/uLAvYA0CpSo}}
\newpage
\section*{Solution}
The answer is $n+n^2$.
This is achieved by doing the following algorithm:
\begin{itemize}
\ii For $i = 1, \dots, n$ erase $2^i$ and $5^i$
and replace both with $1$.
\ii For any of the other $n^2$ other numbers $x$
on the board larger than $1$ after this,
erase $x$ and $1$ and replace both with $1$.
\end{itemize}
To see this is optimal, define the \emph{score}
of a number as $0$ if the number is one,
$1$ if the number is a power of $2$ or a power of $5$ other than $1$,
and $2$ otherwise.
\begin{claim*}
The total score of all numbers decreases by at most $2$ each step.
\end{claim*}
\begin{proof}
Obvious.
\end{proof}
Since the total score to start is $2(n^2+n)$, we are done.
\end{document}