AoPSWiki
Do you have what it takes to be the next brilliant trader, researcher, or developer at Jane Street Capital? Find out in the Careers in Mathematics Forum.

1992 USAMO Problems/Problem 1

From AoPSWiki

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... 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.

Resources

1992 USAMO (Problems)
First Problem 1 2 3 4 5 Followed by
Problem 2
All USAMO Problems and Solutions
Looking for a challenging algebra text? Preparing for MATHCOUNTS or the AMC exams?
Check out Art of Problem Solving's Introduction to Algebra by Richard Rusczyk.
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • FoundationPrivacyContact Us