Each term of a sequence of positive integers is obtained from the previous term by adding to it its largest digit. What is the maximal number of successive odd terms in such a sequence?
Problem
Source: Tournament of Towns Spring 2003 - Junior O-Level - Problem 4
Tags: number theory proposed, number theory
14.06.2011 15:19
amparvardi wrote: Each term of a sequence of positive integers is obtained from the previous term by adding to it its largest digit. What is the maximal number of successive odd terms in such a sequence? Starting number in the odd terms sequence need to end with an odd digit and its max digit must be even in order to allow the next number to be odd too. Max digit cant be $0$ since last digit is odd If max digit is $2$, last digit must be $1$ and next number ends with $3$, so new max digit is $3$ and next number is even and we got two odd subsequent numbers. If max digit is $4$, last digit may be $1$ or $3$ If last digit is $1$, next number ends with $5$ so new max digit is $5$ and next number is even and we got two odd subsequent numbers. If last digit is $3$, next number ends with $7$ so new max digit is $7$ and next number is even and we got two odd subsequent numbers. If max digit is $6$, last digit may be $1$, $3$ or $5$ If last digit is $1$, next number ends with $7$ so new max digit is $7$ and next number is even and we got two odd subsequent numbers. If last digit is $3$, next number ends with $9$ so new max digit is $9$ and next number is even and we got two odd subsequent numbers. If last digit is $5$, next number ends with $1$ and so at most three odd subsequent numbers (see first subcase above). Notice that crossing $10$ adds one to the next digit to the left which cant become a new even max digit (since it was $\le 6$) If last digit is $7$, next number ends with $3$ and so at most three odd subsequent numbers (see second subcase above). Notice that crossing $10$ adds one to the next digit to the left which cant become a new even max digit (since it was $\le 6$) If max digit is $8$, last digit may be $1$, $3$, $5$ or $7$ If last digit is $1$, next number ends with $9$ so new max digit is $9$ and next number is even and we got two odd subsequent numbers. If last digit is $3$, next number ends with $1$ and so at most three odd subsequent numbers (see first subcase above). Notice that crossing $10$ adds one to the next digit to the left which cant become a new even max digit (since it was $\le 8$) If last digit is $5$, next number ends with $3$ and so at most four odd subsequent numbers (see second subcase above). Notice that crossing $10$ adds one to the next digit to the left which cant become a new even max digit (since it was $\le 8$) If last digit is $7$, next number ends with $5$ and so at most five odd subsequent numbers (see third subcase above). Notice that crossing $10$ adds one to the next digit to the left which cant become a new even max digit (since it was $\le 8$) So at most five such subsequent odd numbers. And since $5$ may be reached for example with $807,815,823,831,839$, the answer is $\boxed{5}$