How many positive integers $N$ in the segment $\left[10, 10^{20} \right]$ are such that if all their digits are increased by $1$ and then multiplied, the result is $N+1$? (F. Bakharev)
Problem
Source: 2020 Tuymaada Junior P7
Tags: number theory, Digits
06.10.2020 10:08
in segment $[10,10^{20}]$
06.10.2020 12:45
Claim. For every positive integer $N = \overline{a_n a_{n-1} \ldots a_0}$. The following inequality holds \[N+1 \geq (a_n+1)(a_{n-1}+1) \cdots (a_0+1).\] Proof. We will induct on $n$. It's trivial for $n = 0$ since $N+1 = a_0+1$. Assume that the inequality is true for any positive integer $\overline{a_k a_{k-1} \ldots a_0}$. Now, take a positive integer $N = \overline{a_{k+1} a_{k} \ldots a_0}$. Notice that \begin{align*} N+1 - \prod_{i=0}^{k+1} (a_i+1) &= 10^{k+1}a_{k+1} + \overline{a_k a_{k-1} \ldots a_0}+1 - a_{k+1}\prod_{i=0}^k(a_i+1) - \prod_{i=0}^k (a_i+1) \\ &= a_{k+1}\left(10^{k+1} - \prod_{i=0}^k (a_i+1)\right) + \left(\overline{a_k a_{k-1} \ldots a_0} + 1 - \prod_{i=0}^k (a_i+1)\right) \end{align*}Since $0 \leq a_i \leq 9$ for every $0 \leq i \leq k+1$, then $\prod_{i=0}^k (a_i+1) \leq 10^{k+1}$. Also, by the inducation hypothesis we have $\overline{a_k a_{k-1} \ldots a_0} + 1 \geq \prod_{i=0}^k (a_i+1)$. Thus \[N+1 \geq \prod_{i=0}^{k+1} (a_i+1)\] Now using similar manipulation, we see that for any positive integer $N = \overline{a_n a_{n-1} \ldots a_0}$ satisfying \[N+1 = (a_n+1)(a_{n-1}+1) \cdots (a_0+1)\]we have \[a_n \left(10^n - \prod_{i=0}^{n-1} (a_i+1) \right) + \left(\overline{a_n a_{n-1} \ldots a_0} + 1 - \prod_{i=0}^{n-1} (a_i+1)\right) = 0.\]But since both terms are non-negative, then we have \[10^n = \prod_{i=0}^{n-1} (a_i+1)\]which only holds if $a_i = 9$ for every $0 \leq i \leq n-1$. Thus, $N$ must be of the form $x\underbrace{99 \ldots 9}_n$. It easy to check that $N = x\underbrace{99\ldots 9}_{n}$ satisfies the problem where $1 \leq n \leq 20$ and $x$ be any digit satisfy the problem.
06.10.2020 14:03
Let $N=\overline{a_na_{n-1}\cdots a_1a_0}$. Then $$a_n 10^n + a_{n-1} 10^{n-1} + \cdots + a_0 = (a_n+1)(a_{n-1}+1)\cdots(a_1+1)(a_0+1)=a_n(a_{n-1}+1)(a_{n-2}+1)\cdots(a_0+1)+a_{n-1}(a_{n-2}+1)\cdots(a_0+1)+\cdots+a_1(a_0+1)+a_0$$Each term on the left is at least each term on the right. Equality holds iff $a_{n-1}=a_{n-2}=\cdots=a_0=9$. $a_n$ can be any digit except zero. Hence there are $9\cdot 19=171$ numbers.