For a positive integer $n$ let $S(n)$ be the sum of digits in the decimal representation of $n$. Any positive integer obtained by removing several (at least one) digits from the right-hand end of the decimal representation of $n$ is called a stump of $n$. Let $T(n)$ be the sum of all stumps of $n$. Prove that $n=S(n)+9T(n)$.
Problem
Source: APMO 2001
Tags: induction, number theory, easy
pleurestique
19.03.2006 08:59
induction on the number of digits. base case is easy. assume the relation is true for numbers of $d$ digits and let $n$ be a number of $d+1$ digits, $\overline{z_d...z_2z_1z_0}$, and let $t_i$ denote the stump obtained by deleting the last $i$ digits. then by induction $n = 10t_1+z_0 = 10(9T(t_1)+S(t_1))+z_0 = 90T(t_1)+10S(t_1)+z_0 = 90(T(n) - t_1)+9S(t_1)+S(n) = 9[10(T(n)-t_1)+S(t_1)]+S(n) = 9T(n)+S(n)$. this last equality results from $10(T(n)-t_1) + S(t_1) =z_d0+z_dz_{d-1}0+...+z_d...z_20+z_d+z_{d-1}+...+z_1 = z_d+z_dz_{d-1}+...+z_d...z_2z_1$
t0rajir0u
20.03.2006 00:03
The problem is straightforward without induction. Let $n = d_k d_{k-1} ... d_2 d_1 d_0 = \sum_{i=0}^{k} 10^i d_i$, where $d_i$ are the digits of $n$. Now, $S(n) = \sum_{i=0}^{k} d_i$. As to the value of $T(n)$, note that the $n-m$-digit stump - which we denote $U_m (n)$ - has the form $U_m (n) = \sum_{i=m}^{k} 10^{i-m} d_i$, and $T(n) = \sum_{i=1} U_i (n)$, so $S(n) + 9 T(n) = \sum_{i=0}^{k} \left( 1 + 9( \sum_{j=0}^{k-1} 10^j ) \right) d_i = \sum_{i=0}^{k} 10^i d_i = n$, as desired.
pleurestique
20.03.2006 03:02
yeah, that became evident in the process of writing up the induction...but then i left the proof as it was anyway.
Binomial-theorem
02.05.2012 22:40
Let $n=10^na_n+10^{n-1}a_{n-1}+\cdots a_0=\sum_{i=0}^{n}(10^i*a_i)$.
We therefore have $T(n)=(10^{n-1}a_n+10^{n-2}a_{n-1}+\cdots 10a_2+a_1)$ (removing one digit) $+ (10^{n-2}a_n+10^{n-3}a_{n-1}+\cdots 10a_3+a_2)$ (removing two digits) $+ \cdots +$ $(10a_n+a_{n-1})$. This is the same thing as $T(n)=\sum_{i=0}^{n-1}(10^i)a_n+\sum_{i=0}^{n-2}(10^i)a_{n-1}+\cdots \sum_{i=0}^{1}(10^i)a_2+\sum_{i=0}^{0}(10^i)a_1$. This is the same thing as $\sum_{i=1}^{n}( \sum_{j=0}^{i-1}(10^j)*a_{i})$.
Note that $\sum_{j=0}^{i-1}(10^j)=\frac{1(10^i-1)}{9}$ therefore we get $T(n)=\sum_{i=1}^{n}(\frac{10^i-1}{9}a_i)$.
We also obviously have $S(n)=\sum_{i=0}^{n}(a_i)$. We desire $S(n)+9T(n)=n$. If this is true, then we need $\sum_{i=0}^{n}(a_i)+9*\sum_{i=1}^{n}(\frac{10^i-1}{9}a_i)=\sum_{i=0}^{n}(10^i*a_i)$. Note that $9*\sum_{i=1}^{n}(\frac{10^i-1}{9}a_i)=\sum_{i=1}^{n}((10^i-1)*a_i)$. Adding $\sum_{i=0}^{n}(a_i)$ gives us $a_0+\sum_{i=1}^{n}(10^i*a_i)=10^0*a_0+\sum_{i=1}^{n}(10^i*a_i)=\sum_{i=0}^{n}(10^i*a_i)$ as desired $\blacksquare$.
HoRI_DA_GRe8
31.08.2021 07:52
Nevertheless an easy problem ,just write and sum.
Tafi_ak
06.10.2021 19:59
Let $n=\sum _{i=0}^na_i10^i.$ Now $S(n)+9T(n)=S(n)+9[\sum _{i=0}^{n-1}a_n\times 10^i+\sum _{i=0}^{n-2}a_{n-1}\times 10^{n-2}+\cdots +\sum _{i=0}^{0}a_1\times 10^1]$ $=S(n)+9[\sum _{i=0}^na_n\frac{10^n-1}{9}]$ $=S(n)+ \sum _{i=0}^na_i(10^i-1)$ $=S(n)+ \sum _{i=0}^na_i10^i-S(n)$ $=n$ As desired.
HamstPan38825
05.10.2022 02:00
We may simply induct from $n$ to $n+1$. Let $\nu_{10} (n+1) = k$. If $k = 0$, then $S(n+1) = S(n) + 1$ while $T(n) = T(n+1)$, so we are okay. Otherwise, $S(n)$ decreases by $9k-1$, while $T(n)$ increases by $k$ for each stump for which the value increases by 1. Then$$S(n+1) + 9 T(n+1) = S(n) + 9T(n) -9k+1 + 9k = n+1,$$as needed.
EquationTracker
04.01.2024 18:55
By $m=\overline{x_1x_2\dots x_k}$, we denote the base $10$ representation of a number $m$ such that $x_1,x_2,\ldots,x_k$ are the digits of $m$.
Let $n=\overline{a_1a_2\dots a_n}=a_1\cdot 10^{n-1}+a_2\cdot 10^{n-2}+\dots+a_n$. Then $ S(n)=a_1+a_2+\dots +a_n $. The stumps of $n$ are $\overline{a_1a_2\dots a_{n-1}}$, $\overline{a_1a_2\dots a_{n-2}}$, ... , $\overline{a_1a_2}$, $\overline{a_1}$. So, \[T(n)=\left(a_1\cdot 10^{n-2}+\dots+a_{n-1}\right)+\left(a_1\cdot10^{n-3}+\dots+a_{n-2}\right)+\dots+a_1\]\[\implies T(n)=\underbrace{111\ldots 1}_{(n-1)\text{ times}}\cdot a_1+\underbrace{111\ldots 1}_{(n-2)\text{ times}}\cdot a_2+\dots+ a_{n-1}\]\[\implies 9T(n)=\underbrace{999\ldots 9}_{(n-1)\text{ times}}\cdot a_1+\underbrace{999\ldots 9}_{(n-2)\text{ times}}\cdot a_2+\dots+ 9a_{n-1}\]\[\implies S(n)+9T(n)=a_1\cdot 10^{n-1}+a_2\cdot 10^{n-2}+\dots+10a_{n-1}+a_n=n\]And we are done...