\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{ToT Spring 2010 S-A7}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 86}
\maketitle
\section*{Problem}
A positive integer is written on a blackboard.
In a move, you can put plus signs between some of the digits on the board,
then erase the original number, and write down the resulting sum instead.
Show that you can make the number on the blackboard a single digit within five moves.
\section*{Video}
\href{https://www.youtube.com/watch?v=2hMOwc5Zqrs&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/2hMOwc5Zqrs}}
\section*{External Link}
\url{https://aops.com/community/p1822594}
\newpage
\section*{Solution}
The first move is most of the difficulty of the problem.
\begin{claim*}
We can break the given digit string into blocks of length $1$ and $2$ such that
\begin{itemize}
\ii At most one nonzero digit is in a block of length $1$;
\ii In each block of length $2$, the left digit is nonzero.
\end{itemize}
\end{claim*}
\begin{proof}
Easy; just look at consecutive blocks of nonzero digits
(separated by strings of zeros).
For the even length blocks, use all nonzero digits in pairs;
for the odd length blocks except possibly the last one
(for which there is no zero to the right),
use one of the zeros from the right border.
An example is shown below for illustration.
\[
\boxed{13}0\boxed{46}\boxed{91}\boxed{20}000
\boxed{27}\boxed{10}\boxed{30}00000\boxed{15}3.
\qedhere
\]
\end{proof}
Call a \emph{pair} a block of length $2$.
Let $t$ be the single nonzero remaining digit if it exists, otherwise, let $t = 0$.
Then, let $(a_i, b_i)$ denote all the pairs,
with $a_i$ being the last digit, for $1 \le i \le M$.
If we commit to inserting $+$'s between all the blocks,
then we will get a sum of the form
\[ S(I) = t + \sum_{i \notin I} (a_i + b_i)
+ \sum_{i \in I} (10a_i + b_i) \]
as a function of our indices $I$.
The main claim is this:
\begin{claim*}
We can pick the set $I$ such that
$S(I) = c \cdot 10^e + \eps$ for some integer $1 \le c < 100$, and $0 \le \eps \le 90$.
In other words, $S$ has at most four nonzero digits.
\end{claim*}
\begin{proof}
Define
\begin{align*}
X &= \sum_i \left( a_i + b_i \right) \\
Y &= \sum_i \left( 10a_i + b_i \right).
\end{align*}
It is easy to see $Y \ge 1.9X$,
so the two leading digits of $Y$ and $X$ are different.
From this it follows that the interval
$[X,Y]$ contains a number of the form $c \cdot 10^e$.
Now, if we imagine starting with $I = \varnothing$, so $S(I) = X+t$,
and adding elements one at a time until we get $I = \{1, \dots, M\}$,
where $S(I) = Y+t$.
At each step, $S(I)$ increases at most $81$.
So we take the first moment where $S(I) > c \cdot 10^e$, and this $I$ works.
\end{proof}
Hence after the first step, we get a number with at most four nonzero digits;
if we split all the digits after that, we get a number at most $36$.
In fact, starting from any number at most $36$,
two steps are sufficient to complete the problem (hence four steps total).
\end{document}