1992 USAMO Problems/Problem 1

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$


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1992 USAMO (ProblemsResources)
First Problem Followed by
Problem 2
1 2 3 4 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png