Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This puzzle deals with positive integers in decimal representation. From every integer you can move to one or two or three other integers. The allowed moves for integer $n\ge1$ are as follows:

  • You may double the number (that is, $n$ becomes $2n$).
  • If the rightmost digit in the decimal representation is $4$, you may remove this rightmost digit.
  • If the rightmost digit in the decimal representation is $0$, you may remove this rightmost digit.

For instance, starting with the integer $n=227$ you could make the following moves: $$227\to454\to45\to90\to9\to18\to36\to72\to144\to14\to1\to2\to4$$

Your task: Show that starting with an arbitrary integer $n\ge1$, you can eventually reach the cosmic goal integer $4$ (by repeatedly applying these three moves).

(The title of this puzzle was chosen as repercussion of the "Four is Cosmic!" puzzle.)

share|improve this question
    
I'm pretty sure the same is true for 2 or 8 as well. – Darrel Hoffman Mar 20 at 17:58
    
My suggestion: prove that you can get from n to n-1 in a finite number of moves, use induction down to 4, then provide special cases for 1, 2, and 3 (1 and 2 are trivial, 3 is 3, 6, 12, 24, 2, 4) – hobbs Mar 20 at 19:57
up vote 7 down vote accepted

Let the starting number be $n$. Consider the case where $n < 10$.

$$ \begin{align} 1 &\to 2 \to 4 \\ 2 &\to 4 \\ 3 &\to 6 \to 12 \to 24 \to 2 \to 4\\ 4 \\ 5 &\to 10 \to 1 \to 2 \to 4 \\ 6 &\to 12 \to 24 \to 2 \to 4\\ 7 &\to 14 \to 1 \to 2 \to 4\\ 8 &\to 16 \to 32 \to 64 \to 6 \to 12 \to 24 \to 2 \to 4\\ 9 &\to 18 \to 36 \to 72 \to 144 \to 14 \to 1 \to 2 \to 4 \end{align} $$

Now consider general $n > 0$, not ending with the digit $0$ (remove all trailing zeros before beginning).

Let a step from $n$ be defined as the sequence to get from $n$ to a number $m$ for which exactly one trailing digit is removed. For convenience, we write this functionally as $s(n) = m$. The next step is a step from $m$, and we can extend this to a sequence of steps.

Now, let $n = 10k + d$, where $k$ is an integer and $0 \leq d < 10$.

If $d = 0$, we remove the trailing 0 to get $s(n) = \frac{n}{10}$ .

If $d \in \{1,2,3,6,8\}$, first consider $d=1$. Since $s(n) = \frac{(10k+1)4-4}{10} = 4k$, $s(n)$ is even. Similarly for the other $d$, in each case $s(n)$ is even. Since $n$ is doubled at most 3 times, $s(n) \leq \frac{8n}{10}$ .

If $d=4$, then $s(n) = \frac{(10k+4)-4}{10} = k$, i.e. $s(n) < \frac{n}{10}$ .

If $d=5$, then $s(n) = \frac{(10k+5)2}{10} = 2k+1 = \frac{n}{5}$.

If $d=7$, then $s(n) = \frac{(10k+7)2-4}{10} = 2k+1$, i.e. $s(n) < \frac{n}{5}$ .

If $d=9$, we need more steps. Consider $n = 10k+9$ . We double $n$ four times to get a trailing 4, so $s(n) = \frac{(10k+9)16-4}{10} = 16k+14$, i.e. $s(n) < 1.6n$. The last digit of $s(n)$ is $16k+14$ mod $10$, for which we only need to consider $0 \leq k \leq 9$. Trying all $k$ from 0 to 9, we find $s(n)$ ends with $4,0,6,2,8,4,0,6,2,8$ respectively. In particular, $s(n)$ never ends with 9.

Apply the above iteratively. Recall $s(n) < 1.6n$, and $s(n) \mod 10 \in \{0,2,4,6,8\}$ .

If $s(n)$ ends with 0 or 4, then $s(s(n)) \leq \frac{s(n)}{10} < 0.16n$, so $s(s(n)) < n$ .

Otherwise $s(n)$ ends with 2, 6 or 8.
Let $m=s(s(n))$. Then $m$ is even and $m \leq 0.8s(n) < 1.28n$.

If $m$ ends with 0 or 4, then $s(m) \leq \frac{m}{10} < 0.128n$, so $s(m) < n$.
Otherwise $s(m)$ is even and $s(m) \leq 0.8m < 1.024n$, so $s(s(m)) \leq 0.8s(m) < n$.

In every case, there is a sequence of steps taking $n$ to an integer strictly less than $n$, unless we arrive at 4, in which case we've arrived. Call this sequence a jump. Since $n \neq 0$, we never jump to zero.

The jumps reduce $n$ monotonically, so we eventually arrive at a single digit, from which the table above shows that . By inspection of the table above, steps from single digits the sequence always terminates at 4.

QED

share|improve this answer
    
Just as I said to the other answer, I think it should also be proven that "So from then on, the number always decreases". I don't believe this is sufficient proof. Specifically, when $\frac{16n-4}{10}$ ends in an $8$ you are able to reduce the resulting number by doing $\frac{8n-4}{10}$ but that is still larger than the initial $n$ and at this point you haven't proven that this new number doesn't end with a 9. I know it couldn't be but I think you haven't proven that with this alone – Ivo Beckers Mar 20 at 14:47
    
@IvoBeckers I was assuming the "never ends with 9" comment was understood to automatically invoke the earlier $n \to \frac{8n}{10}$ process. I've now made this explicit. It doesn't matter that the number is higher than the starting $n$, so long as it decreases monotonically at some point. – Lawrence Mar 20 at 14:50
1  
What I'm trying to say is. You haven't proven that the not-ending-with-9 process can't produce numbers ending with a 9. For all we know you have a number ending with a 9, gets turned to a number ending in an 8, gets turned to a number with a 9, and so on forever, and this process does not reduce the number – Ivo Beckers Mar 20 at 14:55
    
@IvoBeckers Ok, let me have a look at this. – Lawrence Mar 20 at 15:00
1  
@IvoBeckers The proof has become less elegant, but I think all cases are covered. I wonder whether it would have been simpler to start with 4 and show that we can reach all integers by running the process backwards. – Lawrence Mar 20 at 16:01

Removing rightmost digit is like dividing the number by $10$ for $0$ and more than $10$ for $4$.

If the last digit of the number you have taken is $0$,$4$ you just divide your number by $10$.

If the last digit is $2,7,5$. You multiply your number by $2$ and divide by $10$ that makes dividing by $5$ after $2$ moves.

If the last digit is $1$,$6$ you multiply twice by $2$ then divide by $10$ that makes dividing by $2.5$, still your number gets less.

If the last digit is $3$,$8$ you need to multiply third time by $2$ then divide $10$ that makes dividing by $1.25$, still your number gets lesser and becomes divided by $1.25$ at the end.

The only time your number gets bigger when your last digit is $9$, that makes your number $1.6$ times bigger than before after removing the last digit. But since the next number's last digit (after removing $4$, which becomes last digit after doubling it $4$ times) cannot be $9$ ($x9\times 16$'s second digit cannot be $9$) the mentioned removing number above will make your number to $4$ whatsoever.

So whatever the number you have taken, there will be a solution.

share|improve this answer
    
I came up with the same conclusions as you although I'm still not convinced yet about the 9. It's true that $x9 \cdot 16$ can't have a 9 in the second digit but it could be an 8 and in that case you can only divide by $1.25$ and $1.6 / 1.25$ is still bigger than one and after that you might possibly get another 9 but I'm not sure. I think you still need to expand a bit on the possibilites when the last digit is 9 – Ivo Beckers Mar 20 at 14:11
    
@IvoBeckers the last digit cannot be 9 again, that's the point. – Oray Mar 20 at 14:19
    
No I mean after doing the next step again. Let's say you have a 9 at the end. you multiply by 1.6 and get a 8 at the end. you then can divide by 1.25. At that point your number didn't get smaller and at this point I'm not sure if you could have a 9 again – Ivo Beckers Mar 20 at 14:22
    
@IvoBeckers it does not matter, i see what u meant but u cannot have 9 as the last digit ever after the last 9 because 94 or 90 as the last 2 digits is impossible after the first removal – Oray Mar 20 at 14:24
    
I think you're right but I also think that it should be proven – Ivo Beckers Mar 20 at 14:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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