10
$\begingroup$

Warmup question:

The number 458 is written on a blackboard. It is allowed either to double the number on the blackboard, or to erase its last digit. How can we obtain the number 14 using these operations? Erasing the last digit is not allowed if the number is a one-digit number. Assume everything is done in base 10.

Example: Starting with 458, after the first step, the blackboard will display either 916 (via doubling) or 45 (via last digit deletion).

Main question:

Using the same transformations as in the warmup question, can we always eventually reach any positive integer N we want to no matter what positive integer M the blackboard starts with?

Attribution:

Warmup question: Mathematical Circles (Russian Experience)

Main question: Me

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
18
$\begingroup$

For the warmup,

keep doubling 458 to get 14656, then erase the last 3 digits to get 14

For the main problem:

We can go from any $M$ to any $N$ as above, with a series of doublings followed by a series of last-digit removals. This requires us to multiply $M$ by some power of 2 so that the result has $N$ as a prefix. This is proven possible in the paper "Every number is the beginning of a power of 2" for powers of 2, though its argument also follows for powers of 2 times any fixed value.
For a heuristic argument: if, say, $N$ has 6 digits, there's about a 1 in a million chance that a "random" $k$-digit number has it as a prefix, regardless of how large $k$ is. So, repeatedly doubling a number, we have a new chance to hit that 1-in-a-million with each new digit count $k$, so at some point we'll hit. More rigorously, hitting the prefix means hitting a fixed-width window in the fractional part of its log base 10, and powers of 2 (or them times a constant) densely cover that unit interval and so exist in that window, since $\log_{10}{2}$ is irrational.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Alternate way to use that paper's result without modification: Qryrgr qbja gb bar qvtvg. Rnpu fvatyr qvtvg ahzore pna or qbhoyrq vagb gur gra gb avargrra enatr. Qryrgr qbja gb bar qvtvg ntnva gb fgneg sebz bar naq uvg rknpgyl gur cbjref bs gjb. $\endgroup$ Commented Oct 11, 2024 at 17:58
  • $\begingroup$ @DanielWagner What a cool idea! I encourage you to write it up as an answer (perhaps changing the upper bound to 18). $\endgroup$ Commented Oct 11, 2024 at 19:12
7
$\begingroup$

Alternatively:

458->45->90->9->18->36->72->144->14.

I found this by considering factors of

the numbers 140 to 149. That $144=12^2=2^4*9$ looked promising, especially as getting 90 and 9 was easy.

Improve this answer
$\endgroup$
3
$\begingroup$

Warmup:

You can get $14$ from $458 \times 2^5$.

Main:

Let the starting number be $x$. If it can be proven that any number can comprise the first digits of an $x \times 2^y$, then it can be.

Take a $d+1$-digit number ($10^{d+1}>=n>=10^d$). If $x$ keeps getting multiplied, eventually $n$ will repeat leading the products. If $x \times 2^y$ and $x \times 2^z$ are led by the same $n$, then $2^{z-y}$ can be used in proving that all leading numbers that are sufficiently (far) smaller (let's call one $m$; $c<d$; $10^{c+1}>=m>=10^c$) can be consecutively reached by using $2^{z-y}$ repeatedly in the multiplications so that no $m$ can be skipped.

This would mean $10^a \times (10^d+1)/10^d >= 2^{z-y} >= 10^a \times 10^d/(10^d+1)$.

If $2^{z-y}$ can make $m$ skip to $m+-2$ or farther, it amounts to multiplying $m$ with $10^{d-c}$ and having another $d+1$ digit apart from $n$, and make it skip even more numbers, which isn't possible. Rinse and repeat with larger and larger initial leading numbers ($n$), and it's proven.

In fact,

The same reasoning applies to every positive integer base other than perfect powers of $10$, not just $2$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.