Olympiad Maths Prep

Library / /2 of 5

Algebra Difficulty 5.7 AIME, harder Prove it Greece

Determine all positive integers which are equal to 1313 times the sum of their digits.

Solution

Let κ\kappa be the number of digits of the integer AA which is equal to 1313 times the sum of its digits. The least possible AA is 10κ110^{\kappa-1}, while the maximal possible sum of the digits is 9κ9\kappa. Therefore we need to have:
10κ1139κ=117κ.(1) 10^{\kappa-1} \leq 13 \cdot 9\kappa = 117\kappa. \qquad (1)
For κ4\kappa \ge 4, we will prove using induction that: 10κ1>117κ10^{\kappa-1} > 117\kappa, that is, relation (1) is not valid. In fact, for κ=4\kappa = 4 we have: 1041=103>1174=46810^{4-1} = 10^3 > 117 \cdot 4 = 468. If 10κ1>117κ10^{\kappa-1} > 117\kappa, for the arbitrary κ>4\kappa > 4, then we get:
10(κ+1)1=10κ=1010κ1>10117κ=11710κ>117(κ+1). 10^{(\kappa+1)-1} = 10^{\kappa} = 10 \cdot 10^{\kappa-1} > 10 \cdot 117\kappa = 117 \cdot 10\kappa > 117 \cdot (\kappa+1).
Therefore the number κ\kappa must be less or equal to 33.

* We have to reject the case κ=1\kappa = 1, since A=α<13αA = \alpha < 13\alpha, with 0<α90 < \alpha \le 9.
* Similarly we reject the case with κ=2\kappa = 2, since A=10α+β<13(α+β)A = 10\alpha + \beta < 13(\alpha + \beta).
* Let κ=3\kappa = 3 and A=αβγ=100α+10β+γA = \overline{\alpha\beta\gamma} = 100\alpha + 10\beta + \gamma, 0<α90 < \alpha \le 9, 0β,γ90 \le \beta, \gamma \le 9.

Then we have:
100α+10β+γ=13(α+β+γ),0<α9,0β,γ9 100\alpha + 10\beta + \gamma = 13 \cdot (\alpha + \beta + \gamma), \quad 0 < \alpha \le 9, 0 \le \beta, \gamma \le 9
87α=3β+12γ,0<α9,0β,γ9 \Leftrightarrow 87\alpha = 3\beta + 12\gamma, \quad 0 < \alpha \le 9, 0 \le \beta, \gamma \le 9
29α=β+4γ,0<α9,0β,γ9 \Leftrightarrow 29\alpha = \beta + 4\gamma, \quad 0 < \alpha \le 9, 0 \le \beta, \gamma \le 9
Since 0β+4γ4529α45α10 \le \beta + 4\gamma \le 45 \Rightarrow 29\alpha \le 45 \Rightarrow \alpha \le 1 (since α0\alpha \ne 0), and hence:
β+4γ=29β=294γ00β=294γ9 \beta + 4\gamma = 29 \Rightarrow \beta = 29 - 4\gamma \ge 0 \Rightarrow 0 \le \beta = 29 - 4\gamma \le 9
294γ205γ294γ{5,6,7} \Rightarrow -29 \le -4\gamma \le -20 \Rightarrow 5 \le \gamma \le \frac{29}{4} \Rightarrow \gamma \in \{5, 6, 7\}
* For γ=5β=9\gamma = 5 \Rightarrow \beta = 9 and A=195A = 195.
* For γ=6β=5\gamma = 6 \Rightarrow \beta = 5 and A=156A = 156.
* For γ=7β=1\gamma = 7 \Rightarrow \beta = 1 and A=117A = 117.

Therefore, the positive integers which are equal to 1313 times the sum of their digits are 117117, 156156, and 195195.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.