Maths Olympiad Prep

Library / /107 of 196

Algebra Difficulty 5.3 AIME, harder Prove it Soviet Union

Problem:

Define the sequence {a}n\{a\}_{n} of positive integers as follows. a1=ma_{1} = m. an+1=ana_{n + 1} = a_{n} plus the product of the digits of ana_{n}. For example, if m=5m = 5, we have 5,10,10,5, 10, 10, \ldots. Is there an mm for which the sequence is unbounded?

Solution

Solution:

Put p(n)p(n) for the product of the digits of nn. We show that, for sufficiently large nn, a sequence starting below it cannot get past the "gap" from 10n10^{n} to 10n+10n110^{n} + 10^{n - 1}. For suppose NN is the last member of the sequence below the gap. Then NN has at most nn digits, so p(N)9np(N) \leq 9^{n}. But for sufficiently large nn (in fact for n21n \geq 21) we have 9n<10n19^{n} < 10^{n - 1}. So N+p(N)<10n+10n1N + p(N) < 10^{n} + 10^{n - 1}. But N+p(N)>10nN + p(N) > 10^{n} by assumption. Hence N+p(N)N + p(N) is sure to have second digit (from the left) zero.
So all further terms of the sequence are the same. But for any mm there is certainly a gap above mm, and, as shown, the sequence will not be able to get beyond it. So it is bounded.

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.