Maths Olympiad Prep

Library / /3 of 31

Number theory Difficulty 5.0 AIME, harder Prove it Italy

Problem:

Determine all positive integers that are equal to 300 times the sum of their digits.

Solution

Solution:

We will show that there is a unique solution, namely n=2700n=2700.

Let nn be a positive integer satisfying the given conditions. We immediately observe that, since nn is a multiple of 300300, and hence of 100100, the units and tens digits of nn must be equal to zero. Suppose then that its decimal representation is n=akak1a200n=a_{k} a_{k-1} \cdots a_{2} 00, where, as usual, the first digit aka_{k} is different from zero. We have
n=10kak+10k1ak1++100a210k n=10^{k} a_{k}+10^{k-1} a_{k-1}+\cdots+100 a_{2} \geq 10^{k}
and, since all digits are less than or equal to 99,
s:=ak+ak1++a29(k1). s:=a_{k}+a_{k-1}+\cdots+a_{2} \leq 9(k-1) .
From the hypothesis n=300sn=300 s we obtain, by the preceding inequalities, 10k3009(k1)=2700(k1)10^{k} \leq 300 \cdot 9(k-1)=2700(k-1). We verify by induction that this last inequality is false for k4k \geq 4: the base step is the verification that 104>27003=810010^{4}>2700 \cdot 3=8100; for the inductive step, suppose that 10k>2700(k1)10^{k}>2700(k-1): then 10k+1>10k2>2700(2k2)>2700(k2)10^{k+1}>10^{k} \cdot 2>2700(2 k-2)>2700(k-2).

It follows that k3k \leq 3. Thus nn is of the form 103a3+102a210^{3} a_{3}+10^{2} a_{2} (in this case a3=0a_{3}=0 would a priori also be allowed, although as we shall see this does not occur). The equation n=300sn=300 s becomes 1000a3+100a2=300a3+300a21000 a_{3}+100 a_{2}=300 a_{3}+300 a_{2}, which in turn simplifies to
7a3=2a2. 7 a_{3}=2 a_{2} .
From this last equation we deduce that 77 is a divisor of a2a_{2}, so the only possibility for having a positive integer is a2=7a_{2}=7 and consequently a3=2a_{3}=2. On the other hand, the number thus found, n=2700n=2700, does indeed satisfy the conditions of the problem.

Want a route through all this instead of 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 translated into English from it; metadata (topic, difficulty) added by this project.