0
$\begingroup$

A three digit number was decreased by the sum of its digits .Then the same operation was carried out with the resulting number,et cetera ,100 times in all .Prove that the final number is zero .

One method is very computational - where we look at the number of times 27,18,9 are removed from the original number (within certain ranges) and find a pattern etc.But this is tedious . Can someone suggest a more elegant proof.

$\endgroup$
  • $\begingroup$ Experimentally, $1210$ is the smallest positive integer which takes more than $100$ steps to get to $0$. For all three-digit numbers, we need at most $79$ steps (but $80$ steps for $1000$). $\endgroup$ – Misha Lavrov May 28 at 16:21
5
$\begingroup$

The result is a number divisible by $9$, because

$$(100x+10y+z)-(x+y+z)=9(11x+y).$$

Being a decreasing process, we "jump" from a multiple of $9$ to a smaller multiple of $9$.

Doing it a hundred times, we necessarily fall on $0$...

...Under the condition that we have started from a number less that $900$ (thanks to Empy2 and quasi for pointing it).

It remains the cases in interval $[900,999]$. Here is a special treatment for them.

Let us denote the interval $[k*100,(k+1)*100)$ as being the slice $S_k$.

Indeed, in fact, the "jumps" are not always from a multiple of $9$ to the immediate multiple of $9$ below it ("small jumps"), but happen to be multiples of $18$ ("large jumps"). Here is in particular what happens when we take a number in the slice $S_9$. It is included in one of the two sequences "coalescent" in $891$ :

$$\begin{cases}994 \rightarrow 972 \rightarrow 954 \rightarrow 936 \rightarrow 918 \rightarrow 900 \searrow \\ \text{} \\ \ \ \ \ \ \ \ \ \ \ \ \ \ 981 \rightarrow 963 \rightarrow 945 \rightarrow 927 \rightarrow 909 \nearrow \end{cases} 891 \rightarrow 873 \rightarrow 855 \rightarrow 837 \rightarrow 819 \rightarrow \ \text{etc.}$$

In slices $S_{9}$ and $S_{8}$, using almost always "large jumps" instead of small jumps, we already "spare" ten small jumps which is what was needed to arrive at $0$ with at most a hundred jumps. It looks me not necessary to explain it with more words, but a graphic will help to capture in a single glance what happens in the cases of three numbers and the associated sequence of "jumps":

  • $999$, the extreme case (already a multiple of $9$, with an exceptional initial jump of $-27$). [blue points],

  • $971$ [red points],

  • $943$ [black points].

We see in particular that the slopes are either $-18$ or $-9$, with a dominance of $-18$ on the left and $-9$ on the right.

This is why the numbers of the last slice $S_9=[900,999]$ need not that much steps to reach value 0 (at most $80$ in fact).

enter image description here

Fig. 1 : Slopes $-18$, dominant in the first part leave progressively the place to slopes $-9$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That only gets us below 100 $\endgroup$ – Empy2 May 28 at 7:43
  • $\begingroup$ So it remains to worry about the cases where the starting number exceeds $900$. $\endgroup$ – quasi May 28 at 7:45
  • $\begingroup$ 999 - 100×9 = 99 $\endgroup$ – Empy2 May 28 at 7:47
  • $\begingroup$ @Empy2 I see. You are right. $\endgroup$ – Jean Marie May 28 at 7:49
  • $\begingroup$ @quasi You are right. $\endgroup$ – Jean Marie May 28 at 7:49
2
$\begingroup$

You want to get to $801$ or less within $11$ steps.
The only multiples of nine above $801$ that don't have a digit sum $18$ or more are $900$ and $810$. So you can get from $963$ or less to $801$ in ten steps.
Check $972$, and check you can reach $972$ in one step.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

For each positive integer $n$, let $s(n)$ denote the sum of the digits of $n$, and let $f(n)=n-s(n)$.

It's clear that for $1\le n\le 9$, we have $s(n)=n$, so $f(n)=0$.

If we compare \begin{align*} n&=d_m10^m+\cdots+10d_1+d_0\\[4pt] s(n)&=d_m{\phantom{10^m}}+\cdots + {\phantom{10}}d_1+d_0\\[4pt] \end{align*} it's clear that for $n > 9$, we have $0 < s(n) < n$, hence $0 < f(n) < n$

Thus, for $n > 9$, $f$ is positive and strictly decreasing.

It follows that the infinite sequence $$f(n),f(f(n)),f(f(f(n)))...$$ eventually reaches zero.

Let $k(n)$ be the number of iterations (number of applications of $f$) until zero is reached.

The problem asks us to show that for $100\le n\le 999$, we have $k(n)\le 100$.

In fact, we can get a stronger result . . .

Claim:$\;$If $n$ is a positive integer with $n\le 999$, then $k(n)\le 83$.

Proof:

It's easy to show that $f(n)$ must be a multiple of $9$, hence if a positive integer $n$ is a multiple of $9$, we have $f(n)\le n-9$.

Let $W$ be the set of nonnegative integers $n\le 999$ such that $s(n)=9$.

If $n$ is a nonnegative integer with $n\le 999$, and $abc$ is the $3$-digit representaion of $n$ with leading zeros allowed (i.e., $n=100a+10b+c$), then $n\in W$ if and only if $a+b+c=9$.

It follows that $|W|$ is the number of nonnegative integer solutions $(a,b,c)$ to the equation $$a+b+c=9$$ hence, by the Stars-and-Bars formula, we get $$|W|=\binom{9+3-1}{3-1}=\binom{11}{2}=55$$ It follows that for the sequence $$f(n),f(f(n)),f(f(f(n))),...$$ at most $55$ of the terms are in $W$.

Thus for $n\le 999$, if after $83$ iterations, zero has not yet been reached, then of the first $83$ gaps between consecutive terms of the sequence $$f(n),f(f(n)),f(f(f(n)),...$$ at most $55$ of those gaps could be equal to $9$, and the rest would necessarily be at least $18$.

Hence the result of iteration $84$ would be at most $$f(n)-\Bigl(55{\,\cdot\,}9+(83-55){\,\cdot\,}18\Bigr)=f(n)-999 < n-999\le 0$$ contradiction.

It follows, as claimed, that for $n\le 999$, we have $k(n)\le 83$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.