Difference between revisions of "2019 AIME II Problems/Problem 9"

Latest revision as of 14:46, 4 January 2024

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$ where $p,q,r$ are primes. No number that is a multiple of $20$ can be expressed in the first form because 20 has two primes in its prime factorization, while the first form has only one, and the only integer divisible by $20$ that has the second form is $2^{9}5$ , which is 2560, 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}$ .

Rephrased for clarity by Afly

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_2(n)$ can be exactly $3$ or $4$ . Because greater exponents of 2 (like $2^9\cdot5$ ) gives numbers greater than 2019, so we just have the cases below.

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$ .

@@ Line 1: / Line 1: @@
-Why are you on this page? You should be preparing for this contest, not wasting your time looking for the solutions!
+==Problem==
+Call a positive integer <math>n</math> <math>k</math>-<i>pretty</i> if <math>n</math> has exactly <math>k</math> positive divisors and <math>n</math> is divisible by <math>k</math>. For example, <math>18</math> is <math>6</math>-pretty. Let <math>S</math> be the sum of positive integers less than <math>2019</math> that are <math>20</math>-pretty. Find <math>\tfrac{S}{20}</math>.
+==Solution 1==
+Every 20-pretty integer can be written in form <math>n = 2^a 5^b k</math>, where <math>a \ge 2</math>, <math>b \ge 1</math>, <math>\gcd(k,10) = 1</math>, and <math>d(n) = 20</math>, where <math>d(n)</math> is the number of divisors of <math>n</math>. Thus, we have <math>20 = (a+1)(b+1)d(k)</math>, using the fact that the divisor function is multiplicative. As <math>(a+1)(b+1)</math> must be a divisor of 20, there are not many cases to check.
+If <math>a+1 = 4</math>, then <math>b+1 = 5</math>. But this leads to no solutions, as <math>(a,b) = (3,4)</math> gives <math>2^3 5^4 > 2019</math>.
+If <math>a+1 = 5</math>, then <math>b+1 = 2</math> or <math>4</math>. The first case gives <math>n = 2^4 \cdot 5^1 \cdot p</math> where <math>p</math> is a prime other than 2 or 5. Thus we have <math>80p < 2019 \implies p = 3, 7, 11, 13, 17, 19, 23</math>. The sum of all such <math>n</math> is <math>80(3+7+11+13+17+19+23) = 7440</math>. In the second case <math>b+1 = 4</math> and <math>d(k) = 1</math>, and there is one solution <math>n = 2^4 \cdot 5^3 = 2000</math>.
+If <math>a+1 = 10</math>, then <math>b+1 = 2</math>, but this gives <math>2^9 \cdot 5^1 > 2019</math>. No other values for <math>a+1</math> work.
+Then we have <math>\frac{S}{20} = \frac{80(3+7+11+13+17+19+23) + 2000}{20} = 372 + 100 = \boxed{472}</math>.
+-scrabbler94
+==Solution 2==
+For <math>n</math> to have exactly <math>20</math> positive divisors, <math>n</math> can only take on certain prime factorization forms: namely, <math>p^{19}, p^9q, p^4q^3, p^4qr</math> where <math>p,q,r</math> are primes. No number that is a multiple of <math>20</math> can be expressed in the first form because 20 has ''two'' primes in its prime factorization, while the first form has only ''one'', and the only integer divisible by <math>20</math> that has the second form is <math>2^{9}5</math>, which is 2560, greater than <math>2019</math>.
+For the third form, the only <math>20</math>-pretty numbers are <math>2^45^3=2000</math> and <math>2^35^4=5000</math>, and only <math>2000</math> is small enough.
+For the fourth form, any number of the form <math>2^45r</math> where <math>r</math> is a prime other than <math>2</math> or <math>5</math> will satisfy the <math>20</math>-pretty requirement. Since <math>n=80r<2019</math>, <math>r\le 25</math>. Therefore, <math>r</math> can take on <math>3, 7, 11, 13, 17, 19,</math> or <math>23</math>.
+Thus, <math>\frac{S}{20}=\frac{2000+80(3+7+11+...+23)}{20}=100+4(3+7+11+...+23)=\boxed{472}</math>.
+Rephrased for clarity by Afly
+==Solution 3==
+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_2(n)</math> can be exactly <math>3</math> or <math>4</math>. Because greater exponents of 2 (like <math>2^9\cdot5</math>) gives numbers greater than 2019, so we just have the cases below.
+. <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.
+. <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>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 answer is <math>\frac{1}{20}(2000+80(3+7+..+23)) = 472</math>.
+==See Also==
+{{AIME box|year=2019|n=II|num-b=8|num-a=10}}
+[[Category: Intermediate Number Theory Problems]]
+{{MAA Notice}}

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

Page

Toolbox

Search