Italian Mathematical Olympiad - February Round

Solution:

The answer is (D). Let us start with a more general observation. Given a positive integer $n \geq 2$, consider the smallest power $2^{a}$ of $2$ that in base $10$ is written with at least $n$ digits. Since $2^{a-1}$ is written with at most $n-1$ digits we have $2^{a-1} \leq 10^{n-1}-1$, and hence $10^{n-1} \leq 2^{a} \leq 2 \cdot 10^{n-1}-1$, where the first inequality follows from the hypothesis that $2^{a}$ is written with at least $n$ digits. The inequalities just written mean exactly that the decimal representation of $2^{a}$ begins with the digit $1$. On the other hand, the next power of $2$, namely $2^{a+1}$, satisfies $2 \cdot 10^{n-1} \leq 2^{a+1} \leq 4 \cdot 10^{n-1}-2$, and hence its first decimal digit is $2$ or $3$. From this it follows immediately that $2^{a}$ is the unique power of $2$ that in base $10$ is written with exactly $n$ digits and whose first digit is equal to $1$. The same obviously holds for powers of $2$ with a single digit: the only one beginning with $1$ is precisely $2^{0}$. We therefore obtain that for every possible length of the decimal representation there exists one and only one power of $2$ whose decimal representation has that length and begins with $1$.

From this it follows that in order to count the desired powers of $2$ we only need to understand how many different lengths occur among the numbers written by Maddalena: for each length there is exactly one power of $2$ that begins with the digit $1$. Since $2^{0}$ has a single digit, it is a matter of understanding how many digits $2^{100}$ has. Observe that $2^{10}=1024>10^{3}$, hence $2^{100}>(10^{3})^{10}=10^{30}$, and therefore $2^{100}$ has at least $31$ digits. Let us now show that $2^{100}$ has exactly $31$ digits, that is, that $2^{100}<10^{31}$. Simplifying a factor $2^{30}$ from both sides, the desired inequality becomes $2^{70}<10 \cdot 5^{30}$. Observe now that $2^{7}=128$ and $5^{3}=125$, so that the inequality can further be rewritten in the form
$$\left(\frac{128}{125}\right)^{10}<10$$
The validity of this inequality can be verified in various ways; one possibility is to observe that $\frac{128}{125}=1+\frac{3}{125}<1+\frac{1}{40}$, from which
$$\left(\frac{128}{125}\right)^{2}<\left(1+\frac{1}{40}\right)^{2}=1+\frac{1}{20}+\frac{1}{1600}<1+\frac{1}{19}$$
and squaring once more
$$\left(\frac{128}{125}\right)^{4}<\left(1+\frac{1}{19}\right)^{2}=1+\frac{2}{19}+\frac{1}{361}<1+\frac{1}{9}$$
Continuing in this way we immediately find $\left(\frac{128}{125}\right)^{8}<2$ and hence $\left(\frac{128}{125}\right)^{10}<\left(\frac{128}{125}\right)^{16}<2^{2}=4<10$ as desired.

Since the numbers written by Maddalena have lengths varying between $1$ and $31$, we obtain that the powers of $2$ beginning with $1$ written by Maddalena are exactly $31$.