Difference between revisions of "2019 AIME I Problems/Problem 9"
Kevinmathz (talk | contribs) (→Solution) |
(→Solution: better view of the pairs of solutions) |
||
(11 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==Problem== |
− | Let <math>\tau (n)</math> denote the number of positive integer divisors of <math>n</math>. Find the sum of the six least positive integers <math>n</math> that are solutions to <math>\tau (n) + \tau (n+1) = 7</math>. | + | Let <math>\tau (n)</math> denote the number of positive integer divisors of <math>n</math> (including <math>1</math> and <math>n</math>). Find the sum of the six least positive integers <math>n</math> that are solutions to <math>\tau (n) + \tau (n+1) = 7</math>. |
==Solution== | ==Solution== | ||
− | In order to obtain a sum of 7, we must have: | + | In order to obtain a sum of <math>7</math>, we must have: |
− | * either a number with 5 divisors (''a fourth power of a prime'') and a number with 2 divisors (''a prime''), or | + | * either a number with <math>5</math> divisors (''a fourth power of a prime'') and a number with <math>2</math> divisors (''a prime''), or |
− | * a number with 4 divisors (''a semiprime'') and a number with 3 divisors (''a square of a prime''). (No integer greater than 1 can have fewer than 2 divisors.) | + | * a number with <math>4</math> divisors (''a semiprime or a cube of a prime'') and a number with <math>3</math> divisors (''a square of a prime''). (No integer greater than <math>1</math> can have fewer than <math>2</math> divisors.) |
− | Since both of these cases contain a number with an odd number of divisors, that number must be an even power of a prime. These can come in the form of a square like <math>3^2</math> with 3 divisors, or a fourth power like <math>2^4</math> with 5 divisors. We then find the smallest such values by hand. | + | Since both of these cases contain a number with an odd number of divisors, that number must be an even power of a prime. These can come in the form of a square-like <math>3^2</math> with <math>3</math> divisors, or a fourth power like <math>2^4</math> with <math>5</math> divisors. We then find the smallest such values by hand. |
− | * <math>2^2</math> has two possibilities: 3 and 4 | + | * <math>2^2</math> has two possibilities: <math>3</math> and <math>4</math> or <math>4</math> and <math>5</math>. Neither works. |
− | * <math>3^2</math> has two possibilities: 8 and 9 | + | * <math>3^2</math> has two possibilities: <math>8</math> and <math>9</math> or <math>9</math> and <math>10</math>. <math>\boxed{(8,9)}</math> and <math>\boxed{(9,10)}</math> both work. |
− | * <math>2^4</math> has two possibilities: 15 and 16 | + | * <math>2^4</math> has two possibilities: <math>15</math> and <math>16</math> or <math>16</math> and <math>17</math>. Only <math>\boxed{(16,17)}</math> works. |
− | * <math>5^2</math> has two possibilities: 24 and 25 | + | * <math>5^2</math> has two possibilities: <math>24</math> and <math>25</math> or <math>25</math> and <math>26</math>. Only <math>\boxed{(25,26)}</math> works. |
− | * <math>7^2</math> has two possibilities: 48 and 49 | + | * <math>7^2</math> has two possibilities: <math>48</math> and <math>49</math> or <math>49</math> and <math>50</math>. Neither works. |
− | * <math>3^4</math> has two possibilities: 80 and 81 | + | * <math>3^4</math> has two possibilities: <math>80</math> and <math>81</math> or <math>81</math> and <math>82</math>. Neither works. |
− | * <math>11^2</math> has two possibilities: 120 and 121 | + | * <math>11^2</math> has two possibilities: <math>120</math> and <math>121</math> or <math>121</math> and <math>122</math>. Only <math>\boxed{(121,122)}</math> works. |
− | * <math>13^2</math> has two possibilities: 168 and 169 | + | * <math>13^2</math> has two possibilities: <math>168</math> and <math>169</math> or <math>169</math> and <math>170</math>. Neither works. |
− | * <math>17^2</math> has two possibilities: 288 and 289 | + | * <math>17^2</math> has two possibilities: <math>288</math> and <math>289</math> or <math>289</math> and <math>290</math>. Neither works. |
− | * <math>19^2</math> has two possibilities: 360 and 361 | + | * <math>19^2</math> has two possibilities: <math>360</math> and <math>361</math> or <math>361</math> and <math>362</math>. Only <math>\boxed{(361,362)}</math> works. |
− | Having computed the working possibilities, we take the sum of the corresponding values of <math>n</math>: <math>8+9+16+25+121+361 = \boxed{540}</math>. ~Kepy. | + | Having computed the working possibilities, we take the sum of the corresponding values of <math>n</math>: <math>8+9+16+25+121+361 = \boxed{\textbf{540}}</math>. ~Kepy. |
− | Possible improvement: since all primes <math>>2</math> are odd, their fourth powers are odd as well, which cannot be adjacent to any primes because both of the adjacent numbers will be even. Thus, we only need to check 16 for the fourth power case. - mathleticguyyy | + | Possible improvement: since all primes <math>>2</math> are odd, their fourth powers are odd as well, which cannot be adjacent to any primes because both of the adjacent numbers will be even. Thus, we only need to check <math>16</math> for the fourth power case. - mathleticguyyy |
− | + | ==Solution 2== | |
+ | Let the ordered pair <math>(a,b)</math> represent the number of divisors of <math>n</math> and <math>n+1</math> respectively. | ||
+ | We see that to obtain a sum of <math>7</math>, we can have <math>(2,5), (3,4), (4,3),</math> and <math>(5,2)</math>. | ||
+ | |||
+ | |||
+ | Case 1: When we have <math>(2,5)</math> | ||
+ | For <math>n</math> to have 2 divisors, it must be a prime number. | ||
+ | For <math>n+1</math> to have 5 divisors, it must be in the form <math>a^4</math>. | ||
+ | If <math>n+1</math> is in the form <math>a^4</math>, then <math>n = a^4-1 = (a^2+1)(a-1)(a+1)</math>. This means that <math>n</math>, or <math>a^4-1</math> has factors other than 1 and itself; <math>n</math> is not prime. | ||
+ | No cases work in this case | ||
+ | |||
+ | |||
+ | Case 2: When we have <math>(4,3)</math> | ||
+ | For <math>n</math> to have 4 divisors, it must be in the form <math>a^3</math> or <math>ab</math>, where <math>a</math> and <math>b</math> are distinct prime numbers . | ||
+ | For <math>n+1</math> to have 3 divisors, it must be a square number. | ||
+ | Let <math>n+1 = A^2</math> (<math>A</math> is a prime number). When <math>n = a^3, a^3+1 = A^2, (A-1)(A+1)=a^3</math>. | ||
+ | We see that the only case when it works is when <math>a=2, A=3</math>, so <math>n=8</math> works. | ||
+ | |||
+ | |||
+ | Case 3: When we have <math>(5,2)</math> | ||
+ | For <math>n</math> to have 5 divisors, it must be in the form <math>a^4</math>, where <math>a</math> is a prime number. | ||
+ | For <math>n+1</math> to have 2 divisors, it must be a prime number. | ||
+ | Notice that <math>a</math> and <math>a^4</math> have the same parity (even/odd). Since every prime greater than 2 are odd, <math>n = a^4</math> must be even. Since <math>a^4</math> is even, <math>a</math> must be even as well, and the only prime number that is even is 2. When <math>a=2, n=16</math>. | ||
+ | |||
+ | |||
+ | Case 4: When we have <math>(3,4)</math> | ||
+ | For <math>n</math> to have 3 divisors, it must be a square number. | ||
+ | For <math>n+1</math> to have 4 divisors, it must be in the form <math>a^3</math> or <math>ab</math>, where <math>a</math> and <math>b</math> are distinct prime numbers. | ||
+ | Similar to Case 2, let <math>n = A^2</math> (<math>A</math> is a prime number). | ||
+ | |||
+ | * When <math>n+1 = a^3, A^2+1 = a^3</math>. | ||
+ | There are no cases that satisfy this equation. | ||
+ | |||
+ | * When <math>n+1=ab, A^2+1 = ab</math>. | ||
+ | We test squares of primes to find values of n that work. | ||
+ | * <math>A=2</math>, <math>4+1=5</math>. Doesn't work. | ||
+ | * <math>A=3</math>, <math>9+1=10=2*5</math>. It works. <math>n=9</math> | ||
+ | * <math>A=5</math>, <math>25+1=26=2*13</math>. It works. <math>n=25</math> | ||
+ | * <math>A=7</math>, <math>49+1=50=2*5^2</math>. Doesn't work. | ||
+ | * <math>A=11</math>, <math>121+1=122=2*61</math>. It works. <math>n=121</math> | ||
+ | * <math>A=13</math>, <math>169+1=170=2*5*17</math>. Doesn't work | ||
+ | * <math>A=17</math>, <math>289+1=290=2*5*29</math>. Doesn't work | ||
+ | * <math>A=19</math>, <math>361+1=362=2*181</math>. It works. <math>n=361</math> | ||
+ | |||
+ | Now we add up the values of <math>n</math> to get the answer: <math>8+16+9+25+121+361 = \boxed{540}</math>. | ||
+ | ~toastybaker | ||
+ | ==Solution 3 (Official MAA)== | ||
+ | Let <math>p,\,q,</math> and <math>r</math> represent primes. Because <math>\tau(n)=1</math> only for <math>n=1,</math> there is no <math>n</math> for which <math>\{\tau(n),\tau(n+1)\}=\{1,6\}</math>. If <math>\{\tau(n),\tau(n+1)\}=\{2,5\},</math> then <math>\{n,n+1\}=\{p,q^4\},</math> so <math>|p-q^4|=1.</math> Checking <math>q=2</math> and <math>p=17</math> yields the solution <math>n=16.</math> If <math>q>2,</math> then <math>q</math> is odd, and <math>p=q^4\pm 1</math> is even, so <math>p</math> cannot be prime. | ||
+ | |||
+ | If <math>\{\tau(n),\tau(n+1)\}=\{3,4\},</math> then <math>\{n,n+1\}=\{p^2,q^3\}</math> or <math>\{p^2,qr\}.</math> Consider <math>|p^2-q^3|=1.</math> If <math>p^2-1=(p-1)(p+1)=q^3,</math> Then <math>q=2.</math> This yields the solution <math>p=3</math> and <math>q=2,</math> so <math>n=8.</math> If <math>q^3-1=(q-1)(q^2+q+1)=p^2,</math> then <math>q-1=1,</math> which does not give a solution. Consider <math>|p^2-qr|=1.</math> If <math>p^2-1=(p-1)(p+1)=qr,</math> then if <math>p>2,</math> the left side is divisible by 8, so there are no solutions. Finding the smallest four primes such that <math>p^2+1=qr</math> gives <math>3^2+1=10,\,5^2+1=26,\,11^2+1=122,</math> and <math>19^2+1=362.</math> The six least values of <math>n</math> are <math>8,9,16,25,121,</math> and <math>361,</math> whose sum is <math>540.</math> | ||
+ | |||
+ | ==Video Solution == | ||
+ | https://www.youtube.com/watch?v=2ouOexOnG1A | ||
+ | |||
+ | ~ North America Math COntest Go Go Go | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2019|n=I|num-b=8|num-a=10}} | {{AIME box|year=2019|n=I|num-b=8|num-a=10}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 07:48, 23 August 2021
Problem
Let denote the number of positive integer divisors of (including and ). Find the sum of the six least positive integers that are solutions to .
Solution
In order to obtain a sum of , we must have:
- either a number with divisors (a fourth power of a prime) and a number with divisors (a prime), or
- a number with divisors (a semiprime or a cube of a prime) and a number with divisors (a square of a prime). (No integer greater than can have fewer than divisors.)
Since both of these cases contain a number with an odd number of divisors, that number must be an even power of a prime. These can come in the form of a square-like with divisors, or a fourth power like with divisors. We then find the smallest such values by hand.
- has two possibilities: and or and . Neither works.
- has two possibilities: and or and . and both work.
- has two possibilities: and or and . Only works.
- has two possibilities: and or and . Only works.
- has two possibilities: and or and . Neither works.
- has two possibilities: and or and . Neither works.
- has two possibilities: and or and . Only works.
- has two possibilities: and or and . Neither works.
- has two possibilities: and or and . Neither works.
- has two possibilities: and or and . Only works.
Having computed the working possibilities, we take the sum of the corresponding values of : . ~Kepy.
Possible improvement: since all primes are odd, their fourth powers are odd as well, which cannot be adjacent to any primes because both of the adjacent numbers will be even. Thus, we only need to check for the fourth power case. - mathleticguyyy
Solution 2
Let the ordered pair represent the number of divisors of and respectively. We see that to obtain a sum of , we can have and .
Case 1: When we have
For to have 2 divisors, it must be a prime number.
For to have 5 divisors, it must be in the form .
If is in the form , then . This means that , or has factors other than 1 and itself; is not prime.
No cases work in this case
Case 2: When we have
For to have 4 divisors, it must be in the form or , where and are distinct prime numbers .
For to have 3 divisors, it must be a square number.
Let ( is a prime number). When .
We see that the only case when it works is when , so works.
Case 3: When we have
For to have 5 divisors, it must be in the form , where is a prime number.
For to have 2 divisors, it must be a prime number.
Notice that and have the same parity (even/odd). Since every prime greater than 2 are odd, must be even. Since is even, must be even as well, and the only prime number that is even is 2. When .
Case 4: When we have
For to have 3 divisors, it must be a square number.
For to have 4 divisors, it must be in the form or , where and are distinct prime numbers.
Similar to Case 2, let ( is a prime number).
- When .
There are no cases that satisfy this equation.
- When .
We test squares of primes to find values of n that work.
- , . Doesn't work.
- , . It works.
- , . It works.
- , . Doesn't work.
- , . It works.
- , . Doesn't work
- , . Doesn't work
- , . It works.
Now we add up the values of to get the answer: . ~toastybaker
Solution 3 (Official MAA)
Let and represent primes. Because only for there is no for which . If then so Checking and yields the solution If then is odd, and is even, so cannot be prime.
If then or Consider If Then This yields the solution and so If then which does not give a solution. Consider If then if the left side is divisible by 8, so there are no solutions. Finding the smallest four primes such that gives and The six least values of are and whose sum is
Video Solution
https://www.youtube.com/watch?v=2ouOexOnG1A
~ North America Math COntest Go Go Go
See Also
2019 AIME I (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.