Difference between revisions of "2021 Fall AMC 12A Problems/Problem 20"
Ehuang0531 (talk | contribs) (Created page with "==Problem== For each positive integer <math>n</math>, let <math>f_1(n)</math> be twice the number of positive integer divisors of <math>n</math>, and for <math>j \ge 2</math>,...") |
m (→Solution 2 (Rigorous reasoning on why there cannot be any other solutions)) |
||
(18 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem== | + | {{duplicate|[[2021 Fall AMC 10A Problems/Problem 23|2021 Fall AMC 10A #23]] and [[2021 Fall AMC 12A Problems/Problem 20|2021 Fall AMC 12A #20]]}} |
+ | |||
+ | == Problem == | ||
For each positive integer <math>n</math>, let <math>f_1(n)</math> be twice the number of positive integer divisors of <math>n</math>, and for <math>j \ge 2</math>, let <math>f_j(n) = f_1(f_{j-1}(n))</math>. For how many values of <math>n \le 50</math> is <math>f_{50}(n) = 12?</math> | For each positive integer <math>n</math>, let <math>f_1(n)</math> be twice the number of positive integer divisors of <math>n</math>, and for <math>j \ge 2</math>, let <math>f_j(n) = f_1(f_{j-1}(n))</math>. For how many values of <math>n \le 50</math> is <math>f_{50}(n) = 12?</math> | ||
<math>\textbf{(A) }7\qquad\textbf{(B) }8\qquad\textbf{(C) }9\qquad\textbf{(D) }10\qquad\textbf{(E) }11</math> | <math>\textbf{(A) }7\qquad\textbf{(B) }8\qquad\textbf{(C) }9\qquad\textbf{(D) }10\qquad\textbf{(E) }11</math> | ||
− | ==Solution== | + | ==Solution 1== |
+ | First, we can test values that would make <math>f(x)=12</math> true. For this to happen <math>x</math> must have <math>6</math> divisors, which means its prime factorization is in the form <math>pq^2</math> or <math>p^5</math>, where <math>p</math> and <math>q</math> are prime numbers. Listing out values less than <math>50</math> which have these prime factorizations, we find <math>12,18,20,28,44,45,50</math> for <math>pq^2</math>, and just <math>32</math> for <math>p^5</math>. Here <math>12</math> especially catches our eyes, as this means if one of <math>f_i(n)=12</math>, each of <math>f_{i+1}(n), f_{i+2}(n), ...</math> will all be <math>12</math>. This is because <math>f_{i+1}(n)=f(f_i(n))</math> (as given in the problem statement), so were <math>f_i(n)=12</math>, plugging this in we get <math>f_{i+1}(n)=f(12)=12</math>, and thus the pattern repeats. Hence, as long as for a <math>i</math>, such that <math>i\leq 50</math> and <math>f_{i}(n)=12</math>, <math>f_{50}(n)=12</math> must be true, which also immediately makes all our previously listed numbers, where <math>f(x)=12</math>, possible values of <math>n</math>. | ||
+ | |||
+ | We also know that if <math>f(x)</math> were to be any of these numbers, <math>x</math> would satisfy <math>f_{50}(n)</math> as well. Looking through each of the possibilities aside from <math>12</math>, we see that <math>f(x)</math> could only possibly be equal to <math>20</math> and <math>18</math>, and still have <math>x</math> less than or equal to <math>50</math>. This would mean <math>x</math> must have <math>10</math>, or <math>9</math> divisors, and testing out, we see that <math>x</math> will then be of the form <math>p^4q</math>, or <math>p^2q^2</math>. The only two values less than or equal to <math>50</math> would be <math>48</math> and <math>36</math> respectively. From here there are no more possible values, so tallying our possibilities we count <math>\boxed{\textbf{(D) }10}</math> values (Namely <math>12,18,20,28,32,36,44,45,48,50</math>). | ||
+ | |||
+ | ~Ericsz | ||
+ | |||
+ | == Solution 2 (''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. | ||
+ | |||
+ | 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</math>. This gives us two cases. First, we have the case where <math>f_1(n) = p^2 \cdot q</math> where <math>p</math> and <math>q</math> are primes. Second, we have the case where <math>f_1(n)=p^5</math> where <math>p</math> is a prime. For both cases, 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. | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:CrazyVideoGamez CrazyVideoGamez] | ||
+ | |||
+ | == Solution 3 == | ||
+ | <math>\textbf{Observation 1}</math>: <math>f_1 \left( 12 \right) = 12</math>. | ||
+ | |||
+ | Hence, if <math>n</math> has the property that <math>f_j \left( n \right) = 12</math> for some <math>j</math>, then <math>f_k \left( n \right) = 12</math> for all <math>k > j</math>. | ||
+ | |||
+ | <math>\textbf{Observation 2}</math>: <math>f_1 \left( 8 \right) = 8</math>. | ||
+ | |||
+ | Hence, if <math>n</math> has the property that <math>f_j \left( n \right) = 8</math> for some <math>j</math>, then <math>f_k \left( n \right) = 8</math> for all <math>k > j</math>. | ||
+ | |||
+ | <math>\textbf{Case 1}</math>: <math>n = 1</math>. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 2</math>, <math>f_2 \left( n \right) = f_1 \left( 2 \right) = 4</math>, <math>f_3 \left( n \right) = f_1 \left( 4 \right) = 6</math>, <math>f_4 \left( n \right) = f_1 \left( 6 \right) = 8</math>. Hence, Observation 2 implies <math>f_{50} \left( n \right) = 8</math>. | ||
+ | |||
+ | <math>\textbf{Case 2}</math>: <math>n</math> is prime. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 4</math>, <math>f_2 \left( n \right) = f_1 \left( 4 \right) = 6</math>, <math>f_3 \left( n \right) = f_1 \left( 6 \right) = 8</math>. Hence, Observation 2 implies <math>f_{50} \left( n \right) = 8</math>. | ||
+ | |||
+ | <math>\textbf{Case 3}</math>: The prime factorization of <math>n</math> takes the form <math>p_1^2</math>. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 6</math>, <math>f_2 \left( n \right) = f_1 \left( 6 \right) = 8</math>. Hence, Observation 2 implies <math>f_{50} \left( n \right) = 8</math>. | ||
+ | |||
+ | <math>\textbf{Case 4}</math>: The prime factorization of <math>n</math> takes the form <math>p_1^3</math>. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 8</math>. Hence, Observation 2 implies <math>f_{50} \left( n \right) = 8</math>. | ||
+ | |||
+ | <math>\textbf{Case 5}</math>: The prime factorization of <math>n</math> takes the form <math>p_1^4</math>. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 10</math>, <math>f_2 \left( n \right) = f_1 \left( 10 \right) = 8</math>. Hence, Observation 2 implies <math>f_{50} \left( n \right) = 8</math>. | ||
+ | |||
+ | <math>\textbf{Case 6}</math>: The prime factorization of <math>n</math> takes the form <math>p_1^5</math>. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 12</math>. Hence, Observation 1 implies <math>f_{50} \left( n \right) = 12</math>. | ||
+ | |||
+ | In this case the only <math>n</math> is <math>2^5 = 32</math>. | ||
+ | |||
+ | <math>\textbf{Case 7}</math>: The prime factorization of <math>n</math> takes the form <math>p_1 p_2</math>. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 8</math>. Hence, Observation 2 implies <math>f_{50} \left( n \right) = 8</math>. | ||
+ | |||
+ | <math>\textbf{Case 8}</math>: The prime factorization of <math>n</math> takes the form <math>p_1 p_2^2</math>. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 12</math>. Hence, Observation 1 implies <math>f_{50} \left( n \right) = 12</math>. | ||
+ | |||
+ | In this case, all <math>n</math> are <math>12, 18, 20, 28, 44, 45,</math> and <math>50</math>. | ||
+ | |||
+ | <math>\textbf{Case 9}</math>: The prime factorization of <math>n</math> takes the form <math>p_1 p_2^3</math>. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 16</math>, <math>f_2 \left( n \right) = f_1 \left( 16 \right) = 10</math>, <math>f_3 \left( n \right) = f_1 \left( 10 \right) = 8</math>. Hence, Observation 2 implies <math>f_{50} \left( n \right) = 8</math>. | ||
+ | |||
+ | <math>\textbf{Case 10}</math>: The prime factorization of <math>n</math> takes the form <math>p_1 p_2^4</math>. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 20</math>, <math>f_2 \left( n \right) = f_1 \left( 20 \right) = 12</math>. Hence, Observation 1 implies <math>f_{50} \left( n \right) = 12</math>. | ||
+ | |||
+ | In this case, the only <math>n</math> is <math>48</math>. | ||
+ | |||
+ | <math>\textbf{Case 11}</math>: The prime factorization of <math>n</math> takes the form <math>p_1^2 p_2^2</math>. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 18</math>, <math>f_2 \left( n \right) = f_1 \left( 18 \right) = 12</math>. Hence, Observation 1 implies <math>f_{50} \left( n \right) = 12</math>. | ||
+ | |||
+ | In this case, the only <math>n</math> is <math>36</math>. | ||
+ | |||
+ | <math>\textbf{Case 12}</math>: The prime factorization of <math>n</math> takes the form <math>p_1 p_2 p_3</math>. | ||
+ | |||
+ | We have <math>f_1 \left( n \right) = 16</math>, <math>f_2 \left( n \right) = f_1 \left( 16 \right) = 10</math>, <math>f_3 \left( n \right) = f_2 \left( 10 \right) = 8</math>. Hence, Observation 2 implies <math>f_{50} \left( n \right) = 8</math>. | ||
+ | |||
+ | Putting all cases together, the number of feasible <math>n \leq 50</math> is <math>\boxed{\textbf{(D) }10}</math>. | ||
+ | |||
+ | ~Steven Chen (www.professorchenedu.com) | ||
+ | |||
+ | ==Video Solution by Mathematical Dexterity== | ||
+ | https://www.youtube.com/watch?v=WQQVjCdoqWI | ||
+ | |||
+ | ==Video Solution by TheBeautyofMath== | ||
+ | https://youtu.be/o2MAmtgBbKc | ||
+ | |||
+ | ~IceMatrix | ||
==See Also== | ==See Also== | ||
{{AMC12 box|year=2021 Fall|ab=A|num-b=19|num-a=21}} | {{AMC12 box|year=2021 Fall|ab=A|num-b=19|num-a=21}} | ||
+ | {{AMC10 box|year=2021 Fall|ab=A|num-b=22|num-a=24}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 15:56, 5 June 2024
- 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 (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. . . This gives us two cases. First, we have the case where where and are primes. Second, we have the case where where is a prime. For both cases, 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.