For positive integers $a$ and $k$, define the sequence $a_1,a_2,\ldots$ by \[a_1=a,\qquad\text{and}\qquad a_{n+1}=a_n+k\cdot\varrho(a_n)\qquad\text{for } n=1,2,\ldots\] where $\varrho(m)$ denotes the product of the decimal digits of $m$ (for example, $\varrho(413)=12$ and $\varrho(308)=0$). Prove that there are positive integers $a$ and $k$ for which the sequence $a_1,a_2,\ldots$ contains exactly $2009$ different numbers.
Problem
Source: Czech-Polish-Slovak Match, 2009
Tags: induction, algebra unsolved, algebra
modularmarc101
27.08.2011 05:16
Let $t$ be the smallest value such that $\varrho(a_t) = 0$, then $a_i = a_t$ for all $i \geq t$ and the sequence stays at one value after $a_t$.
Hence, by the minimality of $t$, we have that $k \cdot \varrho(a_i) > 0$ for all $1 \leq i \leq t-1$, so $a_{i+1} = a_i + k \cdot \varrho(a_i) > a_i$ for all $1 \leq i \leq t$. Therefore, the sequence $a_1,a_2,...,a_{t-1}, a_t$ is strictly increasing and all terms are distinct.
We must prove that there are positive integers $a,k$ such that $t = 2009$ (that is, $\varrho(a_1), \varrho(a_2), ..., \varrho(a_{2008}) \neq 0$ ).
LaChouetteRieuse
27.08.2011 12:36
Here is a somehow nasty solution: The beginning is natural, the end is just some boring calculation I would not have done without my computer.
The trick is first to take
$(a, k) = (4+10^{2004}, \frac{10^{4008}-1}{9}).$
Indeed, by induction, and while $n \leq 2005,$
$a_n = 5 \sum_{k=0}^{n-2}10^k + \sum_{k=n-1}^{2003}10^k + 2 \sum_{k=2004}^{n+2002}10^k $ $+ \sum_{k=n+2003}^{4007}10^k$.
Then, we get sucessively
$a_{2006} = 5 \sum_{k=0}^{2003}10^k + 6 \times 10^{2004} + 2 \sum_{k=2005}^{4007}10^k + 10^{4008},$
$a_{2007} = 5 \sum_{k=0}^{2003}10^k + 8 \times 10^{2004} + 3 \times 10^{2005} + 2 \sum_{k=2006}^{4007}10^k + 4 \times 10^{4008},$
$a_{2008} = 5 \sum_{k=0}^{2003}10^k + 4 \times 10^{2004} + 3 \times 10^{2005} + 3 \times 10^{2006} + 2 \sum_{k=2007}^{4007}10^k +$ $8 \times 10^{4008} + 2 \times 10^{4009},$
$a_{2009} = 5 \sum_{k=0}^{2003}10^k + 2 \times 10^{2004} + 2 \times 10^{2005} + 6 \times 10^{2006} + 2 \sum_{k=2007}^{4007}10^k +$ $0 \times 10^{4008} + 0 \times 10^{4009} + 10^{4010}.$
Therefore, $\varrho(a_{2009}) = 0$ and $a_n = a_{2009}$ when $n \geq 2009$. QED
ThE-dArK-lOrD
01.03.2018 21:43
The above solution is wrong; here's my solution: For convenient, let $\ell =2005$. Choose $a_1=a=\underbrace{11...1}_{2\ell +2}$ and $k=4\underbrace{00...0}_{\ell}1$. We can see that $a_2=\underbrace{11...1}_{\ell}5\underbrace{11...1}_{\ell}2$ and more generally, $$a_{i+1}=\underbrace{11...1}_{\ell+1-i}\underbrace{55...5}_{i}\underbrace{11...1}_{\ell +1-i}\underbrace{22...2}_{i}$$for all $i\in \{ 1,2,...,\ell +1\}$. In particular, we ended with $a_{\ell +2}=\underbrace{55...5}_{\ell +1}\underbrace{22...2}_{\ell +1}$. Then, we've $a_{\ell +3}=\underbrace{55...5}_{\ell +1}\underbrace{22...2}_{\ell +1} +4\underbrace{00...0}_{\ell }1\underbrace{00...0}_{\ell +1}=4\underbrace{55...5}_{\ell}6\underbrace{22...2}_{\ell +1}$. Note that $\varrho (a_{\ell +3})=48\times 10^{\ell}$. And, lastly, $a_{\ell +4}=4\underbrace{55...5}_{\ell}6\underbrace{22...2}_{\ell +1} +192\underbrace{00...0}_{\ell -1}48\underbrace{00...0}_{\ell}=237\underbrace{55...5}_{\ell -2}610\underbrace{22...2}_{\ell }$. After this, the sequence is constant and don't give new different number. In conclusion, we get $\ell +4=2009$ different values, which is required by the problem, done.
AlirezaOpmc
06.03.2018 02:05
The Dark Lord your solution is really cool!