stompjes
Opgave - APMO 2001 vraag 1
Voor een natuurlijk getal $n$, stel $S(n)$ gelijk aan de som van de cijfers van $n$ in decimale voorstelling. Elk natuurlijk getal dat je bekomt door het verwijderen van meerdere (minimum één) cijfers van de rechterkant van de decimale voorstelling van $n$ wordt een stompje van $n$ genoemd. Zij $T(n)$ de som van alle stompjes van $n$. Bewijs dan dat $n=S(n)+9T(n)$.
- login om te reageren
Oplossing
Stel $n=\overline{a_1a_2...a_k}$
$S(n)=a_1+a_2+...+a_k$
en
$T(n)=a_1+\overline{a_1a_2}+...+\overline{a_1a_2...a_{k-1}}$
$=a_1+(10a_1+a_2)+...+(10^{k-2}a_1+10^{k-3}a_2+...+a_{k-1})$
$=\underbrace{11...1}_\text{k-1}a_1+\underbrace{11...1}_\text{k-2}a_2+...+a_{k-1}$
zodat
$S(n)+9T(n)=a_1+a_2+...+a_k+9(\underbrace{11...1}_\text{k-1}a_1+\underbrace{11...1}_\text{k-2}a_2+...+a_{k-1})$
$=a_1+a_2+...+a_k+\underbrace{99...9}_\text{k-1}a_1+\underbrace{99...9}_\text{k-2}a_2+...+9a_{k-1}$
$=10^{k-1}a_1+10^{k-2}a_2+...+a_k$
$=\overline{a_1a_2...a_k}$
$=n$
$\square$
***
Alternatief
We bewijzen dit per inductie op de lengte van het getal.
Voor een getal van $1$ cijfer lang is het triviaal.
Stel dat het bewezen is voor lengte $\le$ $n-1$.
Schrijf $x_n=10*x_{n-1}+a$
Dan is $S(x_n)=S(x_{n-1})+a$ en $T(x_n)=T(x_{n-1})+x_{n-1}$
Bijgevolg is $S(x_n)+9T(x_n)= S(x_{n-1})+a+9T(x_{n-1})+9x_{n-1}=10*x_{n-1}+a$
want $S(x_{n-1})+9T(x_{n-1})=x_{n-1}$ wegens de IH.
Met volledige inductie geldt het dus voor iedere lengte.