Maths Olympiad Prep

Track / Stage 4 / 175 of 340 #1075 of 2604

Problem 1075

AMC 12 late, AIME early
Number theory Difficulty 4.7 Find the answer HMMT November

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

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

Official solution

Let n=2a5bcn=2^{a} 5^{b} c, where 2,5∤c2,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=1−a2a+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 12⋅45\frac{1}{2} \cdot \frac{4}{5} have kk relatively prime to 10, so the answer is 70⋅12⋅45=2870 \cdot \frac{1}{2} \cdot \frac{4}{5}=28.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.