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 I Problems/Problem 9"

(→‎Solution 2)
 
(24 intermediate revisions by 15 users not shown)
Line 1: Line 1:
−
==Problem 9==
+
==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>. 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==
−
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>\boxed{(8,9)}</math> and <math>\boxed{(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>\boxed{(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>\boxed{(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>\boxed{(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>\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{\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 <math>16</math> for the fourth power case. - mathleticguyyy
  
−
~~ paliwalar.21
 
 
==Solution 2==
 
==Solution 2==
−
In order to obtain a sum of 7, we must have:
+
Let the ordered pair <math>(a,b)</math> represent the number of divisors of <math>n</math> and <math>n+1</math> respectively.
−
* either a number with 5 divisors (''a fourth power of a prime'') and a number with 2 divisors (''a prime''), or
+
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>.
−
* 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.
+
Case 1: When we have <math>(2,5)</math>
−
* <math>3^2</math> has two possibilities: 8 and 9, or 9 and 10. (8,9) and (9,10) both work.
+
For <math>n</math> to have 2 divisors, it must be a prime number.
−
* <math>2^4</math> has two possibilities: 15 and 16, or 16 and 17. Only (16,17) works.
+
For <math>n+1</math> to have 5 divisors, it must be in the form <math>a^4</math>.
−
* <math>5^2</math> has two possibilities: 24 and 25, or 25 and 26. Only (25,26) works.
+
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.
−
* <math>7^2</math> has two possibilities: 48 and 49, or 49 and 50. Neither works.
+
No cases work in this case
−
* <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.
+
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 08:21, 4 October 2022

Problem

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$. $\boxed{(8,9)}$ and $\boxed{(9,10)}$ both work.
  • $2^4$ has two possibilities: $15$ and $16$ or $16$ and $17$. Only $\boxed{(16,17)}$ works.
  • $5^2$ has two possibilities: $24$ and $25$ or $25$ and $26$. Only $\boxed{(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 $\boxed{(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 $\boxed{(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{\textbf{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

Solution 2

Let the ordered pair $(a,b)$ represent the number of divisors of $n$ and $n+1$ respectively. We see that to obtain a sum of $7$, we can have $(2,5), (3,4), (4,3),$ and $(5,2)$.


Case 1: When we have $(2,5)$ For $n$ to have 2 divisors, it must be a prime number. For $n+1$ to have 5 divisors, it must be in the form $a^4$. If $n+1$ is in the form $a^4$, then $n = a^4-1 = (a^2+1)(a-1)(a+1)$. This means that $n$, or $a^4-1$ has factors other than 1 and itself; $n$ is not prime. No cases work in this case


Case 2: When we have $(4,3)$ For $n$ to have 4 divisors, it must be in the form $a^3$ or $ab$, where $a$ and $b$ are distinct prime numbers . For $n+1$ to have 3 divisors, it must be a square number. Let $n+1 = A^2$ ($A$ is a prime number). When $n = a^3, a^3+1 = A^2, (A-1)(A+1)=a^3$. We see that the only case when it works is when $a=2, A=3$, so $n=8$ works.


Case 3: When we have $(5,2)$ For $n$ to have 5 divisors, it must be in the form $a^4$, where $a$ is a prime number. For $n+1$ to have 2 divisors, it must be a prime number. Notice that $a$ and $a^4$ have the same parity (even/odd). Since every prime greater than 2 are odd, $n = a^4$ must be even. Since $a^4$ is even, $a$ must be even as well, and the only prime number that is even is 2. When $a=2, n=16$.


Case 4: When we have $(3,4)$ For $n$ to have 3 divisors, it must be a square number. For $n+1$ to have 4 divisors, it must be in the form $a^3$ or $ab$, where $a$ and $b$ are distinct prime numbers. Similar to Case 2, let $n = A^2$ ($A$ is a prime number).

  • When $n+1 = a^3, A^2+1 = a^3$.

There are no cases that satisfy this equation.

  • When $n+1=ab, A^2+1 = ab$.

We test squares of primes to find values of n that work.

  • $A=2$, $4+1=5$. Doesn't work.
  • $A=3$, $9+1=10=2*5$. It works. $n=9$
  • $A=5$, $25+1=26=2*13$. It works. $n=25$
  • $A=7$, $49+1=50=2*5^2$. Doesn't work.
  • $A=11$, $121+1=122=2*61$. It works. $n=121$
  • $A=13$, $169+1=170=2*5*17$. Doesn't work
  • $A=17$, $289+1=290=2*5*29$. Doesn't work
  • $A=19$, $361+1=362=2*181$. It works. $n=361$

Now we add up the values of $n$ to get the answer: $8+16+9+25+121+361 = \boxed{540}$. ~toastybaker

Solution 3 (Official MAA)

Let $p,\,q,$ and $r$ represent primes. Because $\tau(n)=1$ only for $n=1,$ there is no $n$ for which $\{\tau(n),\tau(n+1)\}=\{1,6\}$. If $\{\tau(n),\tau(n+1)\}=\{2,5\},$ then $\{n,n+1\}=\{p,q^4\},$ so $|p-q^4|=1.$ Checking $q=2$ and $p=17$ yields the solution $n=16.$ If $q>2,$ then $q$ is odd, and $p=q^4\pm 1$ is even, so $p$ cannot be prime.

If $\{\tau(n),\tau(n+1)\}=\{3,4\},$ then $\{n,n+1\}=\{p^2,q^3\}$ or $\{p^2,qr\}.$ Consider $|p^2-q^3|=1.$ If $p^2-1=(p-1)(p+1)=q^3,$ Then $q=2.$ This yields the solution $p=3$ and $q=2,$ so $n=8.$ If $q^3-1=(q-1)(q^2+q+1)=p^2,$ then $q-1=1,$ which does not give a solution. Consider $|p^2-qr|=1.$ If $p^2-1=(p-1)(p+1)=qr,$ then if $p>2,$ the left side is divisible by 8, so there are no solutions. Finding the smallest four primes such that $p^2+1=qr$ gives $3^2+1=10,\,5^2+1=26,\,11^2+1=122,$ and $19^2+1=362.$ The six least values of $n$ are $8,9,16,25,121,$ and $361,$ whose sum is $540.$

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. AMC logo.png

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