\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&index=9}{\texttt{https://youtu.be/2hMOwc5Zqrs}}
\newpage
\section*{Solution}
The first move is most of the difficulty of the problem.
\begin{claim*}
We can pair all the digits,
except possibly some zeros and at most one nonzero digit,
into pairs such that in each pair,
the two digits are adjacent,
and the left digit is nonzero.
\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}
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 any pair of digits
which is not in a pair,
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}