10. Maddalena writes on a sheet of paper all the powers of 2 from 1 to $2^{100}$ (inclusive). How many of the numbers she wrote start with 1?
(A) 28 or fewer
(B) 29
(C) 30
(D) 31
(E) 32 or more.
10. The answer is (D). Let's start with a more general observation. Given a positive integer $n \geq 2$, consider the smallest power $2^{a}$ of 2 that can be written in base 10 with at least $n$ digits. Since $2^{a-1}$ can be written with at most $n-1$ digits, we have $2^{a-1} \leq 10^{n-1}-1$, and thus $10^{n-1} \leq 2^{a} \leq 2 \cdot 10^{n-1}-1$, where the first inequality follows from the assumption that $2^{a}$ can be written with at least $n$ digits. The inequalities just written mean exactly that the decimal representation of $2^{a}$ starts with the digit 1. On the other hand, the next power of 2, i.e., $2^{a+1}$, satisfies $2 \cdot 10^{n-1} \leq 2^{a+1} \leq 4 \cdot 10^{n-1}-2$, and thus its first decimal digit is 2 or 3. This immediately implies that $2^{a}$ is the only power of 2 that can be written in base 10 with exactly $n$ digits and whose first digit is 1. The same obviously holds for one-digit powers of 2: the only one that starts with 1 is $2^{0}$. We thus obtain that for each possible length of the decimal representation, there is exactly one power of 2 whose decimal representation has that length and starts with 1.

From this, it follows that to count the desired powers of 2, we only need to understand how many different lengths the numbers written by Maddalena can have: for each length, there is exactly one power of 2 that starts with the digit 1. Since $2^{0}$ has a single digit, we need to determine how many digits $2^{100}$ has. Observe that $2^{10}=1024>10^{3}$, so $2^{100}>(10^{3})^{10}=10^{30}$, and thus $2^{100}$ has at least 31 digits. We now show that $2^{100}$ has exactly 31 digits, i.e., that $2^{100}<10^{31}$. Simplifying a factor of $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 the inequality can 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 again

$$
\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 find immediately $\left(\frac{128}{125}\right)^{8}<2$ and thus $\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 ranging from 1 to 31, we obtain that the powers of 2 that start with 1 and are written by Maddalena are exactly 31.