\section*{Problem 3}

Reduce each of the first billion natural numbers (billion \(=10^{9}\) ) to a single digit by taking its digit sum repeatedly. Do we get more 1 s than \(2 \mathrm{~s}\) ?


\section*{Solution}

Taking digit sums repeatedly gives the remainder after dividing the number by 9 , or 9 if the number is exactly divisible by \(9.10^{9}-1=9 n\), and for any \(\mathrm{r}>=0\) the nine consecutive numbers \(9 \mathrm{r}+1,9 \mathrm{r}+2, \ldots, 9 \mathrm{r}+9\) include just one number giving remainder 1 and one number giving remainder 2. Hence the numbers up to \(10^{9}-1\) give equal numbers of \(1 \mathrm{~s}\) and \(2 \mathrm{~s} .10^{9}\) itself gives 1 , so there is just one more of the \(1 \mathrm{~s}\) than the \(2 \mathrm{~s}\).

