\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{ToT Fall 2012 J-A7}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 97}
\maketitle
\section*{Problem}
Peter and Paul play the following game.
First, Peter chooses some positive integer $a$
with the sum of its digits equal to $2012$.
Paul wants to determine this number,
he knows only that the sum of the digits of Peter's number is $2012$.
On each of his moves Paul chooses a positive integer $x$
and Peter tells him the sum of the digits of $|x - a|$.
What is the minimal number of moves in which Paul
can determine Peter's number for sure?
\section*{Video}
\href{https://www.youtube.com/watch?v=K759pczb7-A&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ&index=7&t=1116s}{\texttt{https://youtu.be/K759pczb7-A}}
\newpage
\section*{Solution}
The answer is $2012$,
and in general, if $2012$ is replaced by $n$ the answer is $n$.
Let $N$ denote Peter's number.
For Paul's algorithm, Paul can start by picking $1$.
Then Peter's reply will be exactly $n-1+9k$,
where $k$ is the number of trailing zeros at the end of $N$.
So, Paul learns the position of the rightmost nonzero digit of $N$.
Now, observe that if Paul increases all his future guesses by $10^k$,
he is essentially playing the same game with $N-10^k$.
This is a number with sum of digits $n-1$,
so induction gets the desired result.
Now we show $n$ moves are needed.
Suppose Peter pre-commits to choosing a number of the form
\[
N =
1 \underbrace{0\dots0}_{a_1}
1 \underbrace{0\dots0}_{a_2}
1 \underbrace{0\dots0}_{a_3}
\dots
1 \underbrace{0\dots0}_{a_n}
\]
and even announces this to Paul.
On Paul's turn, he must start by picking \emph{some} number,
and if his number turns is less than $10^{a_n}$,
he will only learn the value of $a_n$.
The same argument applies with $10^{a_{n-1}+1+a_n}$ on the next turn,
in which Paul's second turn only tells him the value of $a_{n-1}$
if his number is not large enough.
And so on.
This shows that at least $n$ moves are necessary.
\end{document}