Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2019 AIME II Problems/Problem 9"
m (→‎Solution 3)
Line 26: Line 26:
 
==Solution 3==
 
==Solution 3==
  
−
The divisors of <math>20</math> are <math>{1,2,4,5,10,20}</math>. <math>v_n(2)</math> must be <math>\ge 2</math> because <math>20=2^2 \times 5</math>. This means that <math>v_n(2)</math> can be exactly <math>3</math> or <math>4</math>.
+
The divisors of <math>20</math> are <math>{1,2,4,5,10,20}</math>. <math>v_2(n)</math> must be <math>\ge 2</math> because <math>20=2^2 \times 5</math>. This means that <math>v_n(2)</math> can be exactly <math>3</math> or <math>4</math>.
  
−
1. <math>v_n(2) = 3</math>. Then <math>\frac{20}{4}=5=5\times 1</math>. The smallest is <math>2^3*5^4</math> which is <math>> 2019</math>. Hence there are no solution in this case.
+
1. <math>v_2(n) = 3</math>. Then <math>\frac{20}{4}=5=5\times 1</math>. The smallest is <math>2^3*5^4</math> which is <math>> 2019</math>. Hence there are no solution in this case.
  
−
2. <math>v_n(2)=4</math>. Then <math>\frac{20}{5}=4 = 4\times 1 = 2\times 2</math>.
+
2. <math>v_2(n)=4</math>. Then <math>\frac{20}{5}=4 = 4\times 1 = 2\times 2</math>.
 
The <math>4\times 1</math> case gives one solution, <math>2^4 \times 5^3 = 2000</math>.
 
The <math>4\times 1</math> case gives one solution, <math>2^4 \times 5^3 = 2000</math>.
 
The <math>2\times 2</math> case gives <math>2^4\times 5 \times (3+7+11+13+17+19+23)</math>.Using any prime greater than <math>23</math> will make <math>n</math> greater than <math>2019</math>.
 
The <math>2\times 2</math> case gives <math>2^4\times 5 \times (3+7+11+13+17+19+23)</math>.Using any prime greater than <math>23</math> will make <math>n</math> greater than <math>2019</math>.

Revision as of 15:07, 5 February 2023

Problem

Call a positive integer $n$ $k$-pretty if $n$ has exactly $k$ positive divisors and $n$ is divisible by $k$. For example, $18$ is $6$-pretty. Let $S$ be the sum of positive integers less than $2019$ that are $20$-pretty. Find $\tfrac{S}{20}$.

Solution 1

Every 20-pretty integer can be written in form $n = 2^a 5^b k$, where $a \ge 2$, $b \ge 1$, $\gcd(k,10) = 1$, and $d(n) = 20$, where $d(n)$ is the number of divisors of $n$. Thus, we have $20 = (a+1)(b+1)d(k)$, using the fact that the divisor function is multiplicative. As $(a+1)(b+1)$ must be a divisor of 20, there are not many cases to check.

If $a+1 = 4$, then $b+1 = 5$. But this leads to no solutions, as $(a,b) = (3,4)$ gives $2^3 5^4 > 2019$.

If $a+1 = 5$, then $b+1 = 2$ or $4$. The first case gives $n = 2^4 \cdot 5^1 \cdot p$ where $p$ is a prime other than 2 or 5. Thus we have $80p < 2019 \implies p = 3, 7, 11, 13, 17, 19, 23$. The sum of all such $n$ is $80(3+7+11+13+17+19+23) = 7440$. In the second case $b+1 = 4$ and $d(k) = 1$, and there is one solution $n = 2^4 \cdot 5^3 = 2000$.

If $a+1 = 10$, then $b+1 = 2$, but this gives $2^9 \cdot 5^1 > 2019$. No other values for $a+1$ work.

Then we have $\frac{S}{20} = \frac{80(3+7+11+13+17+19+23) + 2000}{20} = 372 + 100 = \boxed{472}$.

-scrabbler94

Solution 2

For $n$ to have exactly $20$ positive divisors, $n$ can only take on certain prime factorization forms: namely, $p^{19}, p^9q, p^4q^3, p^4qr$. No number that is a multiple of $20$ can be expressed in the first form, and the only integer divisible by $20$ that has the second form is $2^{9}5$, which is greater than $2019$.

For the third form, the only $20$-pretty numbers are $2^45^3=2000$ and $2^35^4=5000$, and only $2000$ is small enough.

For the fourth form, any number of the form $2^45r$ where $r$ is a prime other than $2$ or $5$ will satisfy the $20$-pretty requirement. Since $n=80r<2019$, $r\le 25$. Therefore, $r$ can take on $3, 7, 11, 13, 17, 19,$ or $23$.

Thus, $\frac{S}{20}=\frac{2000+80(3+7+11+...+23)}{20}=100+4(3+7+11+...+23)=\boxed{472}$.

Solution 3

The divisors of $20$ are ${1,2,4,5,10,20}$. $v_2(n)$ must be $\ge 2$ because $20=2^2 \times 5$. This means that $v_n(2)$ can be exactly $3$ or $4$.

1. $v_2(n) = 3$. Then $\frac{20}{4}=5=5\times 1$. The smallest is $2^3*5^4$ which is $> 2019$. Hence there are no solution in this case.

2. $v_2(n)=4$. Then $\frac{20}{5}=4 = 4\times 1 = 2\times 2$. The $4\times 1$ case gives one solution, $2^4 \times 5^3 = 2000$. The $2\times 2$ case gives $2^4\times 5 \times (3+7+11+13+17+19+23)$.Using any prime greater than $23$ will make $n$ greater than $2019$.

The answer is $\frac{1}{20}(2000+80(3+7+..+23)) = 472$.

See Also

2019 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 8 		Followed by
Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_9&oldid=188676"