Each term of an infinite sequence of natural numbers is obtained from the previous term by adding to it one of its nonzero digits. Prove that this sequence contains an even number.
Problem
Source:
Tags: floor function, Recursive Sequences
27.09.2007 00:52
Let the sequence be $ a_{1}, a_{2}, a_{3},\ldots$. Define a new sequence $ b_{k}=\lfloor a_{k}/ 10\rfloor$. We note that $ a_{k}+10 > a_{k+1}$, so $ b_{k}+1\geq b_{k+1}$. Thus $ \{b_{i}\}$ only increases by one at a time. Furthermore, the sequence $ \{b_{i}\}$ is unbounded since $ \{a_{i}\}$ is unbounded. Combined, we see that $ \{b_{i}\}$ assumes every integer greater than or equal to $ b_{1}$. Suppose $ b_{1}$ has $ m$ digits with decimal representation $ d_{0}d_{1}d_{2}\ldots d_{m}$. Now define $ d^{\prime}_{k}$ to be the least odd number greater than or equal to $ d_{k}$. It's clear that $ 0\leq d^{\prime}_{k}< 10$ still holds. So $ d^{\prime}_{0}d^{\prime}_{1}d^{\prime}_{2}\ldots d^{\prime}_{m}$ is a decimal representation of a number. Call this number $ b^{\prime}$. Notice that $ b^{\prime}$ has all odd digits, and $ b^{\prime}> b_{1}$. This means that at least one term in the sequence $ \{b_{i}\}$ is equal to $ b^{\prime}$, and thus at least one term in the sequence has all odd digits. Let $ k$ be such that $ b_{k}$ has only odd digits. We prove that $ a_{k}$ is even or $ a_{k+1}$ is even. Suppose $ a_{k}$ is odd. Then $ a_{k}$ ends in an odd digit; call it $ d$. We have $ a_{k}= d+10\cdot b_{k}$. Note that this number has all odd digits. So $ a_{k+1}$ will be $ a_{k}$, an odd number, plus a digit of $ a_{k}$, also odd. Thus $ a_{k+1}$ is even. This finishes the proof.
26.01.2013 10:18
Moreover, we can prove that we can find as long as we want sequences of odd integers.