It is given that $2^{333}$ is a 101-digit number whose first digit is 1. How many of the numbers $2^k$, $1\le k\le 332$ have first digit 4?
Problem
Source: ToT - 2001 Fall Junior A-Level #7
Tags: number theory unsolved, number theory
SAPOSTO
20.08.2011 01:24
If $x$ is not power of two then in the interval $\left(x,2x\right)$ there is exactly one power of two.
Let $x$ be an integer and let $l$ be such that $2^l$ is the greatest power of two smaller than $x$. Then $2x>2\cdot2^l=2^{l+1}$ therefore there there is a power of two between $x$ and $2x$. If there are two such powers, i.e. $2^{l+2}<2x$, then $2^{l+1}<x$ which contradicts to the choice of $l$. So for every $x$ (except powers of two) between $x$ and $2x$ we have exactly one power of two.
So let us examine the number of powers of two between $10^n$ and $10^{n+1}$. One power in $\left(10^n,2\cdot10^{n}\right)$, one in $\left(2\cdot10^n,4\cdot10^{n}\right)$, one in $\left(4\cdot10^n,8\cdot10^{n}\right)$. So at least three powers. Actually if the third power (call it $z$) beggins with $4$ we would have one more power, because $z<5\cdot10^n$ and then $2z<2\cdot5\cdot10^n=10^{n+1}$. So we could have four powers of 2 with the same number of digits (like in ${1,2,4,8}$) and three as well (like in ${16,32,64}$). We can't have 5 powers between $10^n$ and $10^{n+1}$ because if the first is $h$, then the fifth is $16h$ and we will have $10^{n+1}>16h>16\cdot10^n>10\cdot10^n=10^{n+1}$ which is contradiction. Above we showed that if a power beggins with $4$ then there are 3 more powers with the same number of digits as this power. Also if there are four powers with one and the same number of digits, then we would have the third power (call it $v$) in the interval $\left(4\cdot10^n,8\cdot10^{n}\right)$ and if it doesn't beggins with $4$, then $v>5\cdot10^n$, so for the fourth power ($2v$) we have $2v>10^{n+1}$ - contradiction! So we have one-to-one correspondence between the quadraplets of powers of two which have one and the same number of digits and the powers that beggin with $4$. So their number is equal.
Assume there are $y$ triplets with one and the same number of digits and $t$ quadraplets with one and the same number of digits. Then $y+t=100$ and $3y+4t=332$. From the last two we get $t=32$. So the "wanted" number is $32$. We have to note that since $2^{333}$ beggins with $1$ then it is in new quadrplet or triplet. So it isn't included in any of our triplets and quadraplets. I think this description is very long and boring while the solution is much shorter itself but I just didn't manage to write it not that tedious. Despite this I think there still might be something unclear. If so - ask!
I have a question. From which year are these problems from Tournament Of Towns. In the individual topics for each problem your write $2001$ while here is written $2011$.