Азиатско-Тихоокеанская олимпиада по математике 2014 года | Казахстанские олимпиады

Для натурального числа mm обозначим через S(m)S(m) и P(m)P(m) сумму и произведение его цифр, соответственно. Докажите, что для любого натурального nn существуют натуральные числа a1,a2,,ana_1, a_2, \ldots, a_n, удовлетворяющие следующим условиям:

S(a1)<S(a2)<<S(an) и S(ai)=P(ai+1)(i=1,2,,n).S(a_1) < S(a_2) < \dots < S(a_n) \text{ и } S(a_{i}) = P(a_{i+1}) \quad (i = 1,2,\ldots, n).

(Мы полагаем an+1=a1a_{n+1} = a_1.)