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

(Solution 2)
m (Solution: LaTeX)
(12 intermediate revisions by 6 users not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
Essentially, you realize that to get 7 you need an odd amount of divisors + and even amount of divisors. This means that one of our n needs to be a square. Furthermore it must either be a prime squared to get 3 divisors or a prime to the fourth to get 5 divisors. Any more factors in a square would be to large. Thus n/n+1 is in the form p^2 or p^4. The rest of the solution is bashing left to the reader.
+
In order to obtain a sum of <math>7</math>, we must have:
 +
* 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 <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 <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: <math>3</math> and <math>4</math> or <math>4</math> and <math>5</math>. Neither works.
 +
* <math>3^2</math> has two possibilities: <math>8</math> and <math>9</math> or <math>9</math> and <math>10</math>. <math>(8,9)</math> and <math>(9,10)</math> both work.
 +
* <math>2^4</math> has two possibilities: <math>15</math> and <math>16</math> or <math>16</math> and <math>17</math>. Only <math>(16,17)</math> works.
 +
* <math>5^2</math> has two possibilities: <math>24</math> and <math>25</math> or <math>25</math> and <math>26</math>. Only <math>(25,26)</math> works.
 +
* <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: <math>80</math> and <math>81</math> or <math>81</math> and <math>82</math>. Neither works.
 +
* <math>11^2</math> has two possibilities: <math>120</math> and <math>121</math> or <math>121</math> and <math>122</math>. Only <math>(121,122)</math> works.
 +
* <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: <math>288</math> and <math>289</math> or <math>289</math> and <math>290</math>. Neither works.
 +
* <math>19^2</math> has two possibilities: <math>360</math> and <math>361</math> or <math>361</math> and <math>362</math>. Only <math>(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.
  
~~ paliwalar.21
+
 
==Solution 2==
+
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
In order to obtain a sum of 7, we must have:
+
 
* either a number with 5 divisors (''a fourth power of a prime'') and a number with 2 divisors (''a prime''), or
+
Note: Bashing would work for this problem, but it would be very tedious.
* a number with 4 divisors (''a semiprime'') and a number with 3 divisors (''a square of a prime''). (No number greater than 1 can have fewer than 2 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.
 
* <math>2^2</math> has two possibilities: 3 and 4, or 4 and 5. Neither works.
 
* <math>3^2</math> has two possibilities: 8 and 9, or 9 and 10. (8,9) and (9,10) both work.
 
* <math>2^4</math> has two possibilities: 15 and 16, or 16 and 17. Only (16,17) works.
 
* <math>5^2</math> has two possibilities: 24 and 25, or 25 and 26. Only (25,26) works.
 
* <math>7^2</math> has two possibilities: 48 and 49, or 49 and 50. Neither works.
 
* <math>3^4</math> has two possibilities: 80 and 81, or 81 and 82. Neither works.
 
* <math>11^2</math> has two possibilities: 120 and 121, or 121 and 122. Only (121,122) works.
 
Having computed the working possibilities, we sum them: <math>8+9+16+25+121 = \boxed{179}</math>. ~Kepy.
 
  
 
==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}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 13:03, 26 December 2019

Problem 9

Let $\tau (n)$ denote the number of positive integer divisors of $n$. Find the sum of the six least positive integers $n$ that are solutions to $\tau (n) + \tau (n+1) = 7$.

Solution

In order to obtain a sum of $7$, we must have:

  • either a number with $5$ divisors (a fourth power of a prime) and a number with $2$ divisors (a prime), or
  • a number with $4$ divisors (a semiprime or a cube of a prime) and a number with $3$ divisors (a square of a prime). (No integer greater than $1$ can have fewer than $2$ 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 $3^2$ with $3$ divisors, or a fourth power like $2^4$ with $5$ divisors. We then find the smallest such values by hand.

  • $2^2$ has two possibilities: $3$ and $4$ or $4$ and $5$. Neither works.
  • $3^2$ has two possibilities: $8$ and $9$ or $9$ and $10$. $(8,9)$ and $(9,10)$ both work.
  • $2^4$ has two possibilities: $15$ and $16$ or $16$ and $17$. Only $(16,17)$ works.
  • $5^2$ has two possibilities: $24$ and $25$ or $25$ and $26$. Only $(25,26)$ works.
  • $7^2$ has two possibilities: $48$ and $49$ or $49$ and $50$. Neither works.
  • $3^4$ has two possibilities: $80$ and $81$ or $81$ and $82$. Neither works.
  • $11^2$ has two possibilities: $120$ and $121$ or $121$ and $122$. Only $(121,122)$ works.
  • $13^2$ has two possibilities: $168$ and $169$ or $169$ and $170$. Neither works.
  • $17^2$ has two possibilities: $288$ and $289$ or $289$ and $290$. Neither works.
  • $19^2$ has two possibilities: $360$ and $361$ or $361$ and $362$. Only $(361,362)$ works.

Having computed the working possibilities, we take the sum of the corresponding values of $n$: $8+9+16+25+121+361 = \boxed{540}$. ~Kepy.


Possible improvement: since all primes $>2$ 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

Note: Bashing would work for this problem, but it would be very tedious.

See Also

2019 AIME I (ProblemsAnswer KeyResources)
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