Maths Olympiad Prep

Library / /1 of 4

Number theory Difficulty 5.3 AIME, harder Prove it Romania

For every non-negative integer nn, let sns_n be the sum of the digits in the decimal expansion of 2n2^n. Is the sequence (sn)nN(s_n)_{n \in \mathbb{N}} eventually increasing?

Solution

Suppose, if possible, that the sequence is eventually increasing, say from some rank n0n_0 on. Fix a non-negative integer mm such that 6mn06m \ge n_0 to write
{s6m+1s6m+1,s6m+2s6m+1+2,s6m+3s6m+2+4,s6m+4s6m+3+8,s6m+5s6m+4+7,s6m+6s6m+5+5, \begin{cases} s_{6m+1} \ge s_{6m} + 1, \\ s_{6m+2} \ge s_{6m+1} + 2, \\ s_{6m+3} \ge s_{6m+2} + 4, \\ s_{6m+4} \ge s_{6m+3} + 8, \\ s_{6m+5} \ge s_{6m+4} + 7, \\ s_{6m+6} \ge s_{6m+5} + 5, \end{cases}
and deduce thereby that s6m+6s6m+27s_{6m+6} \ge s_{6m} + 27, so
s6m+6ns6m+27n,nN.() s_{6m+6n} \ge s_{6m} + 27n, \quad n \in \mathbb{N}. \quad (*)
On the other hand, the number of non-vanishing digits in the decimal expansion of 26m+6n2^{6m+6n} does not exceed (6m+6n)log102<2m+2n\lceil(6m + 6n)\log_{10} 2\rceil < 2m + 2n, so s6m+6n18m+18ns_{6m+6n} \le 18m + 18n, contradicting (*) for nn large enough. The conclusion follows.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.