For an integer $n\geq 1$ let $a(n)$ denote the total number of carries which arise when adding $2017$ and $n\cdot 2017$. The first few values are given by $a(1)=1$, $a(2)=1$, $a(3)=0$, which can be seen from the following: \begin{align*} 001 &&001 && 000 \\ 2017 &&4034 &&6051 \\ +2017 &&+2017 &&+2017\\ =4034 &&=6051 &&=8068\\ \end{align*}Prove that $$a(1)+a(2)+...+a(10^{2017}-1)=10\cdot\frac{10^{2017}-1}{9}.$$
Problem
Source: Baltic Way 2017 Problem 19
Tags: number theory
MSTang
12.11.2017 03:26
The number of carries when adding the positive integers $x$ and $y$ is given by $\tfrac{1}{9}(s(x) + s(y) - s(x+y))$, where $s(k)$ is the sum of the digits of $k$. Therefore \[a(n) = \tfrac{1}{9}\left(s(2017) + s(2017n) - s(2017(n+1))\right) = \tfrac{10}{9} + \tfrac{1}{9}\left(s(2017n) - s(2017(n+1))\right),\]and the given sum telescopes as \[a(1) + \ldots + a\left(10^{2017} - 1\right) = \frac{10}{9} \left(10^{2017} - 1\right) + s(2017) - s(2017 \cdot 10^{2017}) = \frac{10}{9} \left(10^{2017} - 1\right).\]
rafaello
09.10.2021 02:35
We proceed by induction as we note that the order of summing is not important. Base case $n=1$: Summing $2017$ $10$ times, we get $10$ carries here. Suppose the statement is true for $n-1$, i.e. there are $10\cdot \frac{10^{n-1}-1}{9}$ carries after transformation from $2017$ to $2017\cdot 10^{n-1}$. Note that $2017\cdot 10^{n}$ is same as $2017\cdot 10^{n-1}$ summed $10$ times. Hence, by induction hypothesis, total number of carries here is $$10\cdot (10\cdot \frac{10^{n-1}-1}{9} +1)= 10\cdot (10^{n-1}+\ldots +10+1)=10\cdot \frac{10^n-1}{9}.$$