Difference between revisions of "1992 USAMO Problems/Problem 1"

Latest revision as of 17:52, 27 April 2017

Problem

Find, as a function of $\, n, \,$ the sum of the digits of $9 \times 99 \times 9999 \times \cdots \times \left( 10^{2^n} - 1 \right),$ where each factor has twice as many digits as the previous one.

Solution

The answer is $9 \cdot 2^n$ .

Let us denote the quantity $\prod_{k=0}^n \bigl( 10^{2^k}-1 \bigr)$ as $P_n$ . We wish to find the sum of the digits of $P_n$ .

We first note that $P_{n-1} < \prod_{k=0}^{n-1} 10^{2^k} = 10^{2^n-1},$ so $P_{n-1}$ is a number of at most $2^n$ digits. We also note that the units digit is not equal to zero. We may thus represent $P_{n-1}$ as $\sum_{k=0}^{2^n-1} 10^k d_k ,$ where the $d_k$ are digits and $d_0 \neq 0$ . Then $\begin{align*} P_n &= \bigl( 10^{2^n}-1 \bigr) P_{n-1} = \sum_{k=0}^{2^n-1} - 10^k d_k + \sum_{k=0}^{2^n-1} 10^{2^n+k} d_k \\ &= (10-d_0) + \sum_{k=1}^{2^n-1} 10^k(9-d_k) + 10^{2^n}(d_0-1) + \sum_{k=1}^{2^n-1} 10^{2^n+k} d_k . \end{align*}$ Thus the digits of $P_n$ are $10-d_0, 9-d_1, 9-d_2, \dotsc, 9-d_{2^n-1}, d_0-1, d_1, d_2, \dotsc, d_{2^n-1} ,$ and the sum of these is evidently $9 \cdot 2^n$ , as desired. $\blacksquare$