Each term of a sequence of natural numbers 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:
Tags: modular arithmetic, Recursive Sequences
14.10.2007 01:54
Answer: 5 terms. Let $ A$ be the subsequence containing the maximal number of successive odd terms in the sequence. Assume $ A$ contains more than $ 5$ terms. Then, the first six terms of $ A$, $ t_1,t_2,...,t_6$ are odd. 1. If a term $ k$ ends in $ 9$, the largest digit in this term is $ 9$ so the next term is equal to $ k + 9$ which will end with $ 8$ and will not be odd. Hence, the term following a term ending in $ 9$ is not odd. Now, consider four cases. Case 1 The first term $ t_1$ in $ A$ ends in $ 1$. Because the second term is odd, then we must add an even digit to $ t_1$, so the largest digit of $ t_1$, $ l$, is even, and the following term will end in $ k + 1 > k$ so the third term will end in $ k + 1 + k + 1\pmod {10}$ (as $ k + 1$ will be the largest digit of $ t_1$ as no digits besides the last one will change after adding $ l$ as $ 1 + l\le 9$ if $ l$ is an even digit), which is even, so there are at most two terms in $ A$ which is impossible. Case 2 The first term $ t_1$ in $ A$ ends in $ 3$. If the largest digit of $ t_1$ is $ l$ such that $ l + 3\le 9$ then, the largest digit of $ t_2$ is $ l + 3$ so the last digit of $ t_3$ is $ l + 3 + l + 3\pmod {10}$ which is even. So this case is impossible. Otherwise, $ 3 + l > 9$ so $ l = 8$ but then the last digit of $ t_2$ is $ 1$ and using case 1, there is at most $ 1$ term after that, so at most three consecutive odd terms can exist with the first one ending in $ 3$. Case 3 The first term $ t_1$ in $ A$ ends in $ 5$. If the largest digit of $ t_1$ is $ l$ such that $ l + 5\le 9$ then, the largest digit of $ t_2$ is $ l + 5$ so the last digit of $ t_3$ is $ l + 5 + l + 5\pmod {10}$ which is even. So this case is impossible. Otherwise, $ 3 + l > 9$ so $ l = 6$ but then the last digit of $ t_2$ is $ 1$ and using case 1, there is at most $ 1$ term after that or $ l = 8$ but then the last digit of $ t_2$ is $ 3$ and using case 2, there are at most $ 2$ terms after that, so at most four consecutive odd terms can exist with the first one ending in $ 5$. Case 4 The first term $ t_1$ in $ A$ ends in $ 7$. If the largest digit of $ t_1$ is $ l$ such that $ l + 7\le 9$ then, the largest digit of $ t_2$ is $ l + 7$ so the last digit of $ t_3$ is $ l + 7 + l + 7\pmod {10}$ which is even. So this case is impossible. Otherwise, $ 3 + l > 9$ so $ l = 4$ but then the last digit of $ t_2$ is $ 1$ and using case 1, there is at most $ 1$ term after that or $ l = 6$ but then the last digit of $ t_2$ is $ 3$ and using case 2, there are at most $ 2$ terms after that or $ l = 8$ but then the last digit of $ t_2$ is $ 5$ and using case 3, there are at most $ 3$ terms after that, so at most four consecutive odd terms can exist with the first one ending in $ 7$. If $ t_1$ ends with $ 9$ the next term is even (see beginning of the solution). Therefore, there can exist at most $ 5$ consecutive odd terms. An example when this is the case is the subsequence $ 817, 825,833,831,839$.
29.05.2009 18:34
A simpler approach: Step 1:The last digit of each term is odd so that the largest digit of each term is even Step 2:The largest digit of each term remain the same(each addition at most change the largest digit by $ 1$,but the largest is forever even) Step 3:After at most $ 5$ additions we will obtain the largest digit of one term is $ 9$,which will become the largest digit(but it is odd) So our answer is $ 5$