Maths Olympiad Prep

Library / /210 of 740

, 2018

Number theory Difficulty 4.8 AIME Prove it United States

Problem:

For how many positive integers n100n \leq 100 is it true that 10n10 n has exactly three times as many positive divisors as nn has?

Solution

Solution:

Answer: 28
Let n=2a5bcn=2^{a} 5^{b} c, where 2,5c2,5 \nmid c. Then, the ratio of the number of divisors of 10n10 n to the number of divisors of nn is a+2a+1b+2b+1=3\frac{a+2}{a+1} \frac{b+2}{b+1}=3. Solving for bb, we find that b=1a2a+1b=\frac{1-a}{2 a+1}. This forces (a,b)=(0,1),(1,0)(a, b)=(0,1),(1,0). Therefore, the answers are of the form 2k2 k and 5k5 k whenever gcd(k,10)=1\operatorname{gcd}(k, 10)=1. There are 50 positive numbers of the form 2k2 k and 20 positive numbers of the form 5k5 k less than or equal to 100. Of those 70 numbers, only 1245\frac{1}{2} \cdot \frac{4}{5} have kk relatively prime to 10, so the answer is 701245=2870 \cdot \frac{1}{2} \cdot \frac{4}{5}=28.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.