Difference between revisions of "2019 AIME II Problems/Problem 9"
Scrabbler94 (talk | contribs) (add solution) |
|||
(10 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==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>\ | + | 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== | + | ==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. | 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 = 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) = | + | 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. | 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. | ||
Line 14: | Line 14: | ||
-scrabbler94 | -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>. No number that is a multiple of <math>20</math> can be expressed in the first form, and the only integer divisible by <math>20</math> that has the second form is <math>2^{9}5</math>, which is 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>. | ||
+ | |||
+ | ==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>. | ||
+ | |||
+ | 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. | ||
+ | |||
+ | 2. <math>v_n(2)=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== | ==See Also== | ||
{{AIME box|year=2019|n=II|num-b=8|num-a=10}} | {{AIME box|year=2019|n=II|num-b=8|num-a=10}} | ||
+ | [[Category: Intermediate Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 02:30, 16 February 2021
Problem
Call a positive integer -pretty if has exactly positive divisors and is divisible by . For example, is -pretty. Let be the sum of positive integers less than that are -pretty. Find .
Solution 1
Every 20-pretty integer can be written in form , where , , , and , where is the number of divisors of . Thus, we have , using the fact that the divisor function is multiplicative. As must be a divisor of 20, there are not many cases to check.
If , then . But this leads to no solutions, as gives .
If , then or . The first case gives where is a prime other than 2 or 5. Thus we have . The sum of all such is . In the second case and , and there is one solution .
If , then , but this gives . No other values for work.
Then we have .
-scrabbler94
Solution 2
For to have exactly positive divisors, can only take on certain prime factorization forms: namely, . No number that is a multiple of can be expressed in the first form, and the only integer divisible by that has the second form is , which is greater than .
For the third form, the only -pretty numbers are and , and only is small enough.
For the fourth form, any number of the form where is a prime other than or will satisfy the -pretty requirement. Since , . Therefore, can take on or .
Thus, .
Solution 3
The divisors of are . must be because . This means that can be exactly or .
1. . Then . The smallest is which is . Hence there are no solution in this case.
2. . Then . The case gives one solution, . The case gives .Using any prime greater than will make greater than .
The answer is .
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.