Which Solution Would You Feature? 12/17/2012

This post originally appeared on the Brilliant blog on 12/17/2012.

Below, we present a problem form the 12/10/2012 Algebra and Number Theory set, along with 3 student submitted solutions (none of them have been edited). In the comments section, please vote for the correct solution that you think should be featured, and state your reason for choosing the particular solution. For example "Solution C. Because it made sense." Think also if the solutions are correct, wrong, or missing steps.

All solutions have LaTeX edits to make the math appear properly. These exposition is presented as is, and have not been edited.

Note: I will not reveal who wrote which solution in this blog post. The chosen featured solution will (as always) be credited to the originator.

Problem: We are given that $\log_{10} 2 < 0.302$. How many digits are there in the decimal representation of $5^{500}$?

Solution A

Lemma: The number of digits in an integer x is ceiling(logx), where the base is 10.

Proof: We can find $n$ such that $10^n\leq x\leq 10^(n+1)$. $10^n$ has a $1$ followed by n zeros which makes it have $n+1$ digits. $10^(n+1)$ has a 1 followed by n+1 zeros which makes it have $n+1$ digits. Take the log base $10$ of the inequality to get that: $n \leq \log x\leq n+1$. If the inequality is strict, then taking the log will give an integer in which case, just add one (as shown above). If the inequality is not strict, then the integer x will have the same number of digits as $10^n$. Taking the log will give a number between n and n+1, in which case you must take the ceiling of the number to get the desired n+1 digits. Going back to the problem, $\log 5^{500}=500* \log 5= 500*(1-\log 2) > 500*(1-.302)=349$. Since it is slightly bigger than $349$, the number contains $350$ digits.$_\square$

Solution B

Let $N$ be $5^{500}$. $\log N = \log 5^{500} = 500*\log 5 = 500 * (\log \frac {10} {2})$ $= 500*(\log 10 - \log 2) = 500 - 500 * \log 2 > 500 * 0.302 = 349$.Since $5^{10} = 9765625 < 10^7$, so $\log 5^{500} = \log (5^{10})^{50} < \log (10^7)^{50} = \log 10^{350} = 350$, so $349 < \log 5^{500} < 350$, thus $\log 5^{500}$ has $350$ digits.

Solution C

All logarithms are in base $10$. Let $A = 5^{500} \log A = 500 \log 5 \log A = 500*0.6989 \log A = 349.45 A = 10^{349.45}$, i.e., $350$ digits.$_\square$

Remarks from Calvin

Solution A establishes the lemma, which everyone used to approach this problem. This is something that is useful to know, and is used extremely often in computer science. However, the rest of the proof is incomplete, because he only establishes that $\log 5^{500} > 349$, which doesn't tell us anything about the integer part of $\log 5^{500}$. Had I given that $\log 2 < 0.304$, he would have concluded that the answer is 348. A similar common mistake that is often made by students, is to show that $A \geq 2$, and then conclude that the minimum value of $A$ must be 2 (and no other value).

Solution B by Jianzhi W. managed to establish both bounds. By using $5^{10} < 10^7$, he showed that $\log 5 10^3$ so $\log 2 > 0.3$ and so $\log 5 < 0.7$. Both of these ways are equivalent, but (I feel) that most students (esp computer geeks) will know what $2^{10}$ is as opposed to $5^{10}$. This is the ONLY correct solution out of all student submissions.

Solution C is incorrect, because it uses an unsubstantiated / unfounded 'fact'. There was another 'solution' which said "Google says that $5^{500}$ has 350 digits". These do not constitute a proof, unless we are intimately familiar with the actual workings, and are confident that the error terms carried over do not exceed the degree of accuracy that we need.