Maths Olympiad Prep

Library / /52 of 82

Number theory Difficulty 5.7 AIME, harder Prove it Croatia

Prove that every positive integer dd has a positive multiple nn, such that one can delete one of the non-zero digits of nn to obtain another multiple of dd.

Solution

We will find a number nn in the form 10k(10a+b)+c10^k(10a + b) + c where 0c<10k0 \le c < 10^k and a,ba, b are digits. Deleting the digit bb gives the number n1=10ka+cn_1 = 10^k a + c. Since nn1=10k(9a+b)n - n_1 = 10^k(9a+b), to satisfy the conditions of the problem it is sufficient that dd divides 9a+b9a+b and 10ka+c10^k a + c.

The digit bb can be chosen so that 99 divides dbd-b and we set a=db9a = \frac{d-b}{9}. Then d=9a+bd = 9a+b. Let kk be such that 10k1>d10^{k-1} > d. Then there are integers qq and 0r<d0 \le r < d such that 10ka+10k1=dq+r10^k a + 10^{k-1} = dq + r. If we set c=10k1r>0c = 10^{k-1} - r > 0, then 10ka+c=dq10^k a + c = dq, obviously a number divisible by dd.

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 and solution reproduced as published; topic and difficulty added by this site.