Maths Olympiad Prep

Library / /11 of 31

Number theory Difficulty 6.4 National Olympiad Prove it Italy

Problem:

For every natural number nn with 3 decimal digits (thus with the first digit different from zero), we consider the number n0n_{0} obtained from nn by removing its digits, if any, equal to zero. For example, if n=205n=205 then n0=25n_{0}=25.
Determine the number of integers nn with three digits for which n0n_{0} is a divisor of nn different from nn.

Solution

Solution:

We immediately exclude the case in which nn has all digits different from zero, since in this case we have n0=nn_{0}=n. There remain therefore two possibilities:

1) nn has the third digit equal to zero; the decimal representation of nn is of the type n=ab0n=ab0, n0=abn_{0}=ab and n0nn_{0} \mid n for every choice of a{1,,9}a \in \{1, \ldots, 9\} and of b{0,1,,9}b \in \{0,1, \ldots, 9\}. Regarding this case, there are thus 9×10=909 \times 10 = 90 possibilities for nn.

2) nn has the third digit different from zero but the second equal to zero; in this case nn is written in the form a0ba0b and n0n_{0} in the form abab. Recalling the meaning of decimal notation, we thus look for the cases in which 10a+b10a + b divides 100a+b100a + b. Since certainly 10a+b10a + b divides 10(10a+b)=100a+10b10(10a + b) = 100a + 10b, it is also equivalent to see when 10a+b10a + b divides the difference (100a+10b)(10a+b)=9b(100a + 10b) - (10a + b) = 9b.

Writing k(10a+b)=100a+bk(10a + b) = 100a + b and considering the last decimal digit, we obtain that (k1)b(k-1)b is divisible by 1010, so that at least one of k1k-1 and bb is divisible by 55. Since evidently 1<k<101 < k < 10 and 1b91 \leq b \leq 9, we have that k1=5k-1 = 5 or b=5b = 5.

For k1=5k-1 = 5 we obtain 60a+6b=100a+b60a + 6b = 100a + b, from which b=8ab = 8a and hence a=1a = 1, b=8b = 8. One checks that n=108n = 108 is indeed a solution, since 1818 divides 108108.

For b=5b = 5 we use the equivalent property that 10a+b10a + b divides 9b9b, which becomes 10a+510a + 5 divides 4545; one sees immediately that the divisors of 4545 of the form 10a+510a + 5 with a1a \geq 1 are 1515 and 4545, giving the two solutions n=105n = 105 (1515 divides 105105) and n=405n = 405 (4545 divides 405405).

In conclusion, there are 9090 solutions in case 1) and 33 solutions in case 2), for a total of 9393 solutions.

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.