Difference between revisions of "2019 AIME I Problems/Problem 9"
(→Solution 3 (Official MAA)) |
|||
(2 intermediate revisions by 2 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> | + | |
+ | 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== | ||
Line 8: | Line 9: | ||
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. | 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>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>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>(16,17)</math> works. | + | * <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>(25,26)</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>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>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>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>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>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. | + | * <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. |
Latest revision as of 09:21, 4 October 2022
Problem
Let denote the number of positive integer divisors of
. 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.