The numbers from $11111$ to $99999$ are written in a random order, one after another, forming a single number. Prove that it cannot be a power of $2$.

Question

I found the following problem in a book with advanced math problems for 6th grade that I cannot solve:

All the numbers from $11111$ to $99999$ are written in a random order, one after another, thus forming a single number with $444445$ digits. Prove that regardless what the resulting number is, it cannot be a power of $2$.

I tried various things but could not find any solution.

One of my ideas was to determine the sum of all its digits. 11111 & 99999 = 1+1+1+1+1 + 9+9+9+9+9 = 50 11112 & 99998 = 1+1+1+1+2 + 9+9+9+9+8 = 50 ... 55555 = 25

So we have 44444 pairs whose sum of digits is 50 and un unpaired number, 55555 whose sum of digits is 25.

Therefore, the sum of all the digits is 44444 * 50 + 25 = 2222225.

However, I don't know how to prove that no power of 2 has the sum of its digits equal to 2222225.

Any help is appreciate.

Answer 1

Observe that $10 ^5 - 1 = 99999 = 9 \times 11111$.

Hint: Show that the resulting number is a multiple of $11111$, hence is not a power of 2.

---

Phrased in modular arithmetic, there is an easy proof (just work through it). The difficulty is expressing that to a 6th grader (and expecting them to come up with it).

Let $f(i)$ denote which position $i$ appears in.
Then, $S = \sum_{i=11111}^{99999} i 10^{5 f(i) }$.
Since $ 10^5 - 1 = 99999$, so $10^{5f(i) } \equiv 1 \pmod{99999}$ and $ S \equiv \sum_{i=11111}^{99999} i \pmod{99999}$.
This is an invariant, which strongly suggests that we study it and work modulo a factor of 99999.

When summing up the arithmetic progression, observe that $11111 + 99999 = 11111 \times 10 $.
Hence, $ S \equiv 0 \pmod{11111}$, so cannot be a power of 2.

This also explains why trying modulo $3$ or $9$ didn't immediately work. However, if we added in the terms $10000$ to $11110$, then mod 3 would work. This version would have been a great question for a 6th grader.

This generalizes as follows: The concatenation of terms from $\frac{10^n - 1} { 9} $ to $10^n - 1$ in any order is a multiple of $ \frac{10^n-1}{9}$, hence never a power of 2.

Answer 2

You can use digital sums, but there is a subtle trick.

In base 10, the sum of digits rule works modulo $10-1=9$. More generally in base $b$, it works modulo $b-1$.

Let $b=10^5$ so that each "digit" from $11111$ through $99999$ is represented as a single digit of our number base $10^5$. In this rendering the sum of digits must be a multiple of $55555$, for this is the average of all the "digits" in our selected base $10^5$.

Now $10^5-1$ is a multiple of $11111$, so the digit-sum test works for that divisor, and we have just seen that the digit sum of the given number is divisible by $55555=5×11111$. So our number is a multiple of $11111$, which is impossible for a power of $2$!

We can go further. The smallest prime factor of $11111$ is $41$, so if our long number is to be a perfect power at all the base must be at least $41$. Since $11111$ is square-free, we can increase this bound to $11111$ itself.