9
$\begingroup$

For a positive integer n there are two operations defined:

  1. append one of the digits 0, 4 or 8 at the right end of n
  2. n can be divided by 2 if n is even

Start number is 4. Is it possible to construct any positive integer with those two rules?

Example to construct 55: 4→44→22→220→110→55

$\endgroup$
0
11
$\begingroup$

The answer is

yes.

Easy proof:

Do it back to front: Start with the desired number, multiply by 2 until the last digit is 0,4 or 8 and strike out the last digit and start over if necessary. As we can easily check this is always possible with at most 3 doublings each cycle decreases the number so we must eventually arrive at a single digit. Again, it is easily verified that from there we can get to 4.

$\endgroup$
0
8
$\begingroup$

It

is

possible to construct every positive integer this way. Proof:

Suppose not, and let $n$ be the smallest positive integer you can't construct. First of all, $n$ is more than one digit long because all single-digit positive integers are constructible. (4 -> 2 -> 1 -> 10 -> 5; 2 -> 24 -> 12 -> 6 -> 3; 1 -> 14 -> 7; 1 -> 18 -> 9; 6 -> 64 -> 32 -> 16 -> 8.) So $n=10m+d$ where $d$ is its last digit and $m$ is also a positive integer. In particular $m$ is constructible since $m<n$ and hence so are $10m+0,4,8$ so we know that $d$ isn't any of those. Likewise, $2m$ is constructible since $2m<n$ and hence so is $(10\cdot2m+4)/2=10m+2$; $4m$ is constructible since $4m<n$ and hence so is $(10\cdot4m+4)/4=10m+1$. So $d$ isn't any of $0,1,2,4,8$. $4m+2$ is constructible since $4m+2<n$ and hence so is $(10\cdot(4m+2)+4)/4=10m+6$; $8m+2$ is constructible since $8m+2<n$ and hence so is $(10\cdot(8m+2)+4)/4=10m+3$. So $d$ isn't any of $0,1,2,3,4,6,8$. $2m+1$ is constructible, hence so are $(20m+10,14,18)/2=10m+5,7,9$ so $d$ isn't any of $5,7,9$. And that's all the possible last digits, so we're done.

$\endgroup$
3
  • $\begingroup$ Did you just beat me to it by 11 secs? $\endgroup$
    – loopy walt
    Apr 1 at 23:53
  • $\begingroup$ It sure looks like it :-). Your proof is cleaner than mine, though. (Well, of course they're basically the same proof. But I went the route of showing all the cases separately, which I think was suboptimal given that one can summarize the process more neatly and uniformly as you did.) $\endgroup$
    – Gareth McCaughan
    Apr 2 at 0:17
  • $\begingroup$ Thanks! As pretexts (for not deleting my answer) go this is good enough for me ;-) $\endgroup$
    – loopy walt
    Apr 2 at 0:23

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.