The natural number $n$ can be replaced by $ab$ if $a + b = n$, where $a$ and $b$ are natural numbers. Can the number $2001$ be obtained from $22$ after a sequence of such replacements?
Problem
Source: ToT - 2001 Spring Junior O-Level #1
Tags: induction, number theory unsolved, number theory
17.08.2011 17:40
my answer is:yes! lemma: $n+k$ can be replaced by $n$ for any positive integers $n$ and $k$ notice that: $n+1$ can be replaced by $n*1=n$ ,so by a simple induction: $n+k$ can be replaced by $n$ for any positive integers $n$ and $k$. so: all we need is to attain something higher than $2001$ then we can use what i noticed and get $2001$ as desired! we have: $22=11+11$ so it can be replaced by $11*11=121$ , and $121=101+20$ so it can be replaced by $101*20=2020=2001+19$. all we have now to do,is to use the lemma for $n=2001$ and $k=19$.
07.05.2015 21:17
I don't think so. Here is why: when we replace n by another number m, n and m must have the same mod 9 because if n= a+.b, m =10^c *a+b, and 10^c = 1mod 9
07.05.2015 21:37
$ab$ means $a \cdot b$, not the concatenation of $a$ and $b$ (e.g. $a=1, b=21$ gives $m=21$, not $m=121$).
10.07.2016 15:27
constantin07's idea is nice! I solved it similarly to puzzle problem. 22(1,21) 21(1,20) 20(3,17) 51(2,49) 98(29,69) 2001 finished
17.05.2022 21:03
Heres a weird analogy,note that we can move from $n $ to $n-1$ by the steps,so move from $22$ to $14$. Then \begin{align*}14 &=12+2 \rightarrow 24 \\ &=23+1\rightarrow 23 \\ &=20+3\rightarrow 60 \rightarrow 59 \\ &=57+2\rightarrow 114\rightarrow 113 \\ &=22+91\rightarrow 2002 \rightarrow 2001\text{ } \blacksquare \end{align*}
18.05.2022 00:28
Call $n$ good if it can be obtained from $22$ after a finite sequence of replacements. First, note that if $n+1$ is good for some $n$, then $n\cdot1$ is also good. So if we get a good number larger than $2001$, $2001$ must be good, by repeating this operation enough times. Then $22=11+11$ implies $121$ is good, while $121=100+21$ implies that $2100$ is good, and since $2100>2001$ this is enough.