Difference between revisions of "2021 Fall AMC 12A Problems/Problem 20"
(Add a rigorous solution) |
(→Solution 2 (*Rigorous* reasoning on why there cannot be any other solutions)) |
||
Line 13: | Line 13: | ||
~Ericsz | ~Ericsz | ||
− | == Solution 2 ( | + | == Solution 2 (\textit{Rigorous} reasoning on why there cannot be any other solutions) == |
First, take note that the maximum possible value of <math>f_1(n)</math> for <math>1 \le n \le k</math> increases as <math>k</math> increases (it is a step function), i.e. it is increasing. Likewise, as <math>k</math> decreases, the maximum possible value of <math>f_1(n)</math> decreases as well. Also, let <math>f_1(n) = 2d(n)</math> where <math>d(n)</math> is the number of divisors of n. | First, take note that the maximum possible value of <math>f_1(n)</math> for <math>1 \le n \le k</math> increases as <math>k</math> increases (it is a step function), i.e. it is increasing. Likewise, as <math>k</math> decreases, the maximum possible value of <math>f_1(n)</math> decreases as well. Also, let <math>f_1(n) = 2d(n)</math> where <math>d(n)</math> is the number of divisors of n. | ||
Since <math>n \le 50</math>, <math>f_1(n) <= 20</math>. This maximum occurs when <math>d(n) = 10 \implies n = 2^4 \cdot 3 = 48</math>. Next, since <math>f_1(n) <=20</math>, <math>f_1(f_1(n)) \le 12 \implies f_2(n) \le 12</math>. This maximum occurs when <math>d(f_1(n)) = 6 \implies n = 2 \cdot 3^2 = 18, n = 2^2 \cdot 3 = 12</math>. Since <math>f_2(n) \le 12</math>, <math>f_1(f_2(n)) \le 12 \implies f_3(n) \le 12</math>, once again. This maximum again occurs when <math>d(f_2(n)) = 6 \implies f_2(n) = 2^2 \cdot 3 = 12</math>. Now, suppose for the sake of contradiction that <math>f_2(n) < 12</math>. Then, <math>f_3(n) < 12</math> (since <math>f_2(n) = 12</math> was the only number that would maximize <math>f_3(n))</math> for <math>f_2(n) \le 12</math>). As a result, since <math>f_1(n)</math> is increasing, and because <math>12</math> is where <math>f_1</math> steps down from a maximum of <math>6 \cdot 2 = 12</math>, we must have that <math>f_1(f_3(n)) < f_1(12) = 12 \implies f_4(n) < 12</math>. We continue applying <math>f_1</math> on both sides (which is possible since <math>f_1</math> is increasing) until we reach <math>f_50</math>, giving us that <math>f_50(n) < 12</math>. However, <math>f_50(n) = 12</math>, which is a contradiction. Thus, <math>f_2(n) = 12</math>. | Since <math>n \le 50</math>, <math>f_1(n) <= 20</math>. This maximum occurs when <math>d(n) = 10 \implies n = 2^4 \cdot 3 = 48</math>. Next, since <math>f_1(n) <=20</math>, <math>f_1(f_1(n)) \le 12 \implies f_2(n) \le 12</math>. This maximum occurs when <math>d(f_1(n)) = 6 \implies n = 2 \cdot 3^2 = 18, n = 2^2 \cdot 3 = 12</math>. Since <math>f_2(n) \le 12</math>, <math>f_1(f_2(n)) \le 12 \implies f_3(n) \le 12</math>, once again. This maximum again occurs when <math>d(f_2(n)) = 6 \implies f_2(n) = 2^2 \cdot 3 = 12</math>. Now, suppose for the sake of contradiction that <math>f_2(n) < 12</math>. Then, <math>f_3(n) < 12</math> (since <math>f_2(n) = 12</math> was the only number that would maximize <math>f_3(n))</math> for <math>f_2(n) \le 12</math>). As a result, since <math>f_1(n)</math> is increasing, and because <math>12</math> is where <math>f_1</math> steps down from a maximum of <math>6 \cdot 2 = 12</math>, we must have that <math>f_1(f_3(n)) < f_1(12) = 12 \implies f_4(n) < 12</math>. We continue applying <math>f_1</math> on both sides (which is possible since <math>f_1</math> is increasing) until we reach <math>f_50</math>, giving us that <math>f_50(n) < 12</math>. However, <math>f_50(n) = 12</math>, which is a contradiction. Thus, <math>f_2(n) = 12</math>. | ||
− | Now, let us finally solve for the solutions. <math>f_2(n) = 12 \implies f_1(f_1(n)) = 12 \implies d(f_1(n)) = 6</math>. <math>d(f_1(n)) = 6 \implies f_1(n) = p^2 \cdot q</math> where <math>p</math> and <math>q</math> are primes. Since <math>f_1(n) \le 20</math>, <math>f_1(n)</math> can only be <math>12</math>, <math>18</math>, or <math>20</math>. If <math>f_1(n) = 12</math>, then <math>d(n) = 6 \implies n = p^5, p^2 \cdot q \implies n \in \{ 12, 18, 20, 28, 32, 44, 45, 50 \}</math>, resulting in 8 solutions. If <math>f_1(n) = 18</math>, then <math>d(n) = 9 \implies n = p^8, p^2 \cdot q^2 \implies n = 36</math>, giving us one more solution. Finally, <math>f_1(n) = 20 \implies d(n) = 10 \implies n = p^9, p^4 \cdot q \implies n = 48</math>. Thus, in total, we have <math>\boxed{\textbf{(D)} 10}</math> solutions. | + | Now, let us finally solve for the solutions. <math>f_2(n) = 12 \implies f_1(f_1(n)) = 12 \implies d(f_1(n)) = 6</math>. <math>d(f_1(n)) = 6 \implies f_1(n) = p^2 \cdot q</math> where <math>p</math> and <math>q</math> are primes. Since <math>f_1(n) \le 20</math>, <math>f_1(n)</math> can only be <math>12</math>, <math>18</math>, or <math>20</math>. If <math>f_1(n) = 12</math>, then <math>d(n) = 6 \implies n = p^5, p^2 \cdot q \implies n \in \{ 12, 18, 20, 28, 32, 44, 45, 50 \}</math>, resulting in 8 solutions. If <math>f_1(n) = 18</math>, then <math>d(n) = 9 \implies n = p^8, p^2 \cdot q^2 \implies n = 36</math>, giving us one more solution. Finally, <math>f_1(n) = 20 \implies d(n) = 10 \implies n = p^9, p^4 \cdot q \implies n = 48</math>. Thus, in total, we have <math>\boxed{\textbf{(D)} 10}</math> solutions. |
+ | |||
== Solution 3 == | == Solution 3 == | ||
<math>\textbf{Observation 1}</math>: <math>f_1 \left( 12 \right) = 12</math>. | <math>\textbf{Observation 1}</math>: <math>f_1 \left( 12 \right) = 12</math>. |
Revision as of 16:05, 25 November 2023
- The following problem is from both the 2021 Fall AMC 10A #23 and 2021 Fall AMC 12A #20, so both problems redirect to this page.
Contents
Problem
For each positive integer , let
be twice the number of positive integer divisors of
, and for
, let
. For how many values of
is
Solution 1
First, we can test values that would make true. For this to happen
must have
divisors, which means its prime factorization is in the form
or
, where
and
are prime numbers. Listing out values less than
which have these prime factorizations, we find
for
, and just
for
. Here
especially catches our eyes, as this means if one of
, each of
will all be
. This is because
(as given in the problem statement), so were
, plugging this in we get
, and thus the pattern repeats. Hence, as long as for a
, such that
and
,
must be true, which also immediately makes all our previously listed numbers, where
, possible values of
.
We also know that if were to be any of these numbers,
would satisfy
as well. Looking through each of the possibilities aside from
, we see that
could only possibly be equal to
and
, and still have
less than or equal to
. This would mean
must have
, or
divisors, and testing out, we see that
will then be of the form
, or
. The only two values less than or equal to
would be
and
respectively. From here there are no more possible values, so tallying our possibilities we count
values (Namely
).
~Ericsz
Solution 2 (\textit{Rigorous} reasoning on why there cannot be any other solutions)
First, take note that the maximum possible value of for
increases as
increases (it is a step function), i.e. it is increasing. Likewise, as
decreases, the maximum possible value of
decreases as well. Also, let
where
is the number of divisors of n.
Since ,
. This maximum occurs when
. Next, since
,
. This maximum occurs when
. Since
,
, once again. This maximum again occurs when
. Now, suppose for the sake of contradiction that
. Then,
(since
was the only number that would maximize
for
). As a result, since
is increasing, and because
is where
steps down from a maximum of
, we must have that
. We continue applying
on both sides (which is possible since
is increasing) until we reach
, giving us that
. However,
, which is a contradiction. Thus,
.
Now, let us finally solve for the solutions. .
where
and
are primes. Since
,
can only be
,
, or
. If
, then
, resulting in 8 solutions. If
, then
, giving us one more solution. Finally,
. Thus, in total, we have
solutions.
Solution 3
:
.
Hence, if has the property that
for some
, then
for all
.
:
.
Hence, if has the property that
for some
, then
for all
.
:
.
We have ,
,
,
. Hence, Observation 2 implies
.
:
is prime.
We have ,
,
. Hence, Observation 2 implies
.
: The prime factorization of
takes the form
.
We have ,
. Hence, Observation 2 implies
.
: The prime factorization of
takes the form
.
We have . Hence, Observation 2 implies
.
: The prime factorization of
takes the form
.
We have ,
. Hence, Observation 2 implies
.
: The prime factorization of
takes the form
.
We have . Hence, Observation 1 implies
.
In this case the only is
.
: The prime factorization of
takes the form
.
We have . Hence, Observation 2 implies
.
: The prime factorization of
takes the form
.
We have . Hence, Observation 1 implies
.
In this case, all are
and
.
: The prime factorization of
takes the form
.
We have ,
,
. Hence, Observation 2 implies
.
: The prime factorization of
takes the form
.
We have ,
. Hence, Observation 1 implies
.
In this case, the only is
.
: The prime factorization of
takes the form
.
We have ,
. Hence, Observation 1 implies
.
In this case, the only is
.
: The prime factorization of
takes the form
.
We have ,
,
. Hence, Observation 2 implies
.
Putting all cases together, the number of feasible is
.
~Steven Chen (www.professorchenedu.com)
Video Solution by Mathematical Dexterity
https://www.youtube.com/watch?v=WQQVjCdoqWI
Video Solution by TheBeautyofMath
~IceMatrix
See Also
2021 Fall AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 19 |
Followed by Problem 21 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
2021 Fall AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 22 |
Followed by Problem 24 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.