Difference between revisions of "2021 Fall AMC 12A Problems/Problem 20"

Revision as of 15: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.

Problem

For each positive integer $n$ , let $f_1(n)$ be twice the number of positive integer divisors of $n$ , and for $j \ge 2$ , let $f_j(n) = f_1(f_{j-1}(n))$ . For how many values of $n \le 50$ is $f_{50}(n) = 12?$

$\textbf{(A) }7\qquad\textbf{(B) }8\qquad\textbf{(C) }9\qquad\textbf{(D) }10\qquad\textbf{(E) }11$

Solution 1

First, we can test values that would make $f(x)=12$ true. For this to happen $x$ must have $6$ divisors, which means its prime factorization is in the form $pq^2$ or $p^5$ , where $p$ and $q$ are prime numbers. Listing out values less than $50$ which have these prime factorizations, we find $12,18,20,28,44,45,50$ for $pq^2$ , and just $32$ for $p^5$ . Here $12$ especially catches our eyes, as this means if one of $f_i(n)=12$ , each of $f_{i+1}(n), f_{i+2}(n), ...$ will all be $12$ . This is because $f_{i+1}(n)=f(f_i(n))$ (as given in the problem statement), so were $f_i(n)=12$ , plugging this in we get $f_{i+1}(n)=f(12)=12$ , and thus the pattern repeats. Hence, as long as for a $i$ , such that $i\leq 50$ and $f_{i}(n)=12$ , $f_{50}(n)=12$ must be true, which also immediately makes all our previously listed numbers, where $f(x)=12$ , possible values of $n$ .

We also know that if $f(x)$ were to be any of these numbers, $x$ would satisfy $f_{50}(n)$ as well. Looking through each of the possibilities aside from $12$ , we see that $f(x)$ could only possibly be equal to $20$ and $18$ , and still have $x$ less than or equal to $50$ . This would mean $x$ must have $10$ , or $9$ divisors, and testing out, we see that $x$ will then be of the form $p^4q$ , or $p^2q^2$ . The only two values less than or equal to $50$ would be $48$ and $36$ respectively. From here there are no more possible values, so tallying our possibilities we count $\boxed{\textbf{(D) }10}$ values (Namely $12,18,20,28,32,36,44,45,48,50$ ).

~Ericsz

Solution 2 (Rigorous reasoning on why there cannot be any other solutions)

First, take note that the maximum possible value of $f_1(n)$ for $1 \le n \le k$ increases as $k$ increases (it is a step function), i.e. it is increasing. Likewise, as $k$ decreases, the maximum possible value of $f_1(n)$ decreases as well. Also, let $f_1(n) = 2d(n)$ where $d(n)$ is the number of divisors of n.

Since $n \le 50$ , $f_1(n) <= 20$ . This maximum occurs when $d(n) = 10 \implies n = 2^4 \cdot 3 = 48$ . Next, since $f_1(n) <=20$ , $f_1(f_1(n)) \le 12 \implies f_2(n) \le 12$ . This maximum occurs when $d(f_1(n)) = 6 \implies n = 2 \cdot 3^2 = 18, n = 2^2 \cdot 3 = 12$ . Since $f_2(n) \le 12$ , $f_1(f_2(n)) \le 12 \implies f_3(n) \le 12$ , once again. This maximum again occurs when $d(f_2(n)) = 6 \implies f_2(n) = 2^2 \cdot 3 = 12$ . Now, suppose for the sake of contradiction that $f_2(n) < 12$ . Then, $f_3(n) < 12$ (since $f_2(n) = 12$ was the only number that would maximize $f_3(n))$ for $f_2(n) \le 12$ ). As a result, since $f_1(n)$ is increasing, and because $12$ is where $f_1$ steps down from a maximum of $6 \cdot 2 = 12$ , we must have that $f_1(f_3(n)) < f_1(12) = 12 \implies f_4(n) < 12$ . We continue applying $f_1$ on both sides (which is possible since $f_1$ is increasing) until we reach $f_50$ , giving us that $f_50(n) < 12$ . However, $f_50(n) = 12$ , which is a contradiction. Thus, $f_2(n) = 12$ .

Now, let us finally solve for the solutions. $f_2(n) = 12 \implies f_1(f_1(n)) = 12 \implies d(f_1(n)) = 6$ . $d(f_1(n)) = 6 \implies f_1(n) = p^2 \cdot q$ where $p$ and $q$ are primes. Since $f_1(n) \le 20$ , $f_1(n)$ can only be $12$ , $18$ , or $20$ . If $f_1(n) = 12$ , then $d(n) = 6 \implies n = p^5, p^2 \cdot q \implies n \in \{ 12, 18, 20, 28, 32, 44, 45, 50 \}$ , resulting in 8 solutions. If $f_1(n) = 18$ , then $d(n) = 9 \implies n = p^8, p^2 \cdot q^2 \implies n = 36$ , giving us one more solution. Finally, $f_1(n) = 20 \implies d(n) = 10 \implies n = p^9, p^4 \cdot q \implies n = 48$ . Thus, in total, we have $\boxed{\textbf{(D)} 10}$ solutions.

Solution 3

$\textbf{Observation 1}$ : $f_1 \left( 12 \right) = 12$ .

Hence, if $n$ has the property that $f_j \left( n \right) = 12$ for some $j$ , then $f_k \left( n \right) = 12$ for all $k > j$ .

$\textbf{Observation 2}$ : $f_1 \left( 8 \right) = 8$ .

Hence, if $n$ has the property that $f_j \left( n \right) = 8$ for some $j$ , then $f_k \left( n \right) = 8$ for all $k > j$ .

$\textbf{Case 1}$ : $n = 1$ .

We have $f_1 \left( n \right) = 2$ , $f_2 \left( n \right) = f_1 \left( 2 \right) = 4$ , $f_3 \left( n \right) = f_1 \left( 4 \right) = 6$ , $f_4 \left( n \right) = f_1 \left( 6 \right) = 8$ . Hence, Observation 2 implies $f_{50} \left( n \right) = 8$ .

$\textbf{Case 2}$ : $n$ is prime.

We have $f_1 \left( n \right) = 4$ , $f_2 \left( n \right) = f_1 \left( 4 \right) = 6$ , $f_3 \left( n \right) = f_1 \left( 6 \right) = 8$ . Hence, Observation 2 implies $f_{50} \left( n \right) = 8$ .

$\textbf{Case 3}$ : The prime factorization of $n$ takes the form $p_1^2$ .

We have $f_1 \left( n \right) = 6$ , $f_2 \left( n \right) = f_1 \left( 6 \right) = 8$ . Hence, Observation 2 implies $f_{50} \left( n \right) = 8$ .

$\textbf{Case 4}$ : The prime factorization of $n$ takes the form $p_1^3$ .

We have $f_1 \left( n \right) = 8$ . Hence, Observation 2 implies $f_{50} \left( n \right) = 8$ .

$\textbf{Case 5}$ : The prime factorization of $n$ takes the form $p_1^4$ .

We have $f_1 \left( n \right) = 10$ , $f_2 \left( n \right) = f_1 \left( 10 \right) = 8$ . Hence, Observation 2 implies $f_{50} \left( n \right) = 8$ .

$\textbf{Case 6}$ : The prime factorization of $n$ takes the form $p_1^5$ .

We have $f_1 \left( n \right) = 12$ . Hence, Observation 1 implies $f_{50} \left( n \right) = 12$ .

In this case the only $n$ is $2^5 = 32$ .

$\textbf{Case 7}$ : The prime factorization of $n$ takes the form $p_1 p_2$ .

We have $f_1 \left( n \right) = 8$ . Hence, Observation 2 implies $f_{50} \left( n \right) = 8$ .

$\textbf{Case 8}$ : The prime factorization of $n$ takes the form $p_1 p_2^2$ .

We have $f_1 \left( n \right) = 12$ . Hence, Observation 1 implies $f_{50} \left( n \right) = 12$ .

In this case, all $n$ are $12, 18, 20, 28, 44, 45,$ and $50$ .

$\textbf{Case 9}$ : The prime factorization of $n$ takes the form $p_1 p_2^3$ .

We have $f_1 \left( n \right) = 16$ , $f_2 \left( n \right) = f_1 \left( 16 \right) = 10$ , $f_3 \left( n \right) = f_1 \left( 10 \right) = 8$ . Hence, Observation 2 implies $f_{50} \left( n \right) = 8$ .

$\textbf{Case 10}$ : The prime factorization of $n$ takes the form $p_1 p_2^4$ .

We have $f_1 \left( n \right) = 20$ , $f_2 \left( n \right) = f_1 \left( 20 \right) = 12$ . Hence, Observation 1 implies $f_{50} \left( n \right) = 12$ .

In this case, the only $n$ is $48$ .

$\textbf{Case 11}$ : The prime factorization of $n$ takes the form $p_1^2 p_2^2$ .

We have $f_1 \left( n \right) = 18$ , $f_2 \left( n \right) = f_1 \left( 18 \right) = 12$ . Hence, Observation 1 implies $f_{50} \left( n \right) = 12$ .

In this case, the only $n$ is $36$ .

$\textbf{Case 12}$ : The prime factorization of $n$ takes the form $p_1 p_2 p_3$ .

We have $f_1 \left( n \right) = 16$ , $f_2 \left( n \right) = f_1 \left( 16 \right) = 10$ , $f_3 \left( n \right) = f_2 \left( 10 \right) = 8$ . Hence, Observation 2 implies $f_{50} \left( n \right) = 8$ .

Putting all cases together, the number of feasible $n \leq 50$ is $\boxed{\textbf{(D) }10}$ .

~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

@@ Line 13: / Line 13: @@
 ~Ericsz
-== Solution 2 ==
+== 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 \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 ==
 <math>\textbf{Observation 1}</math>: <math>f_1 \left( 12 \right) = 12</math>.

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

Page

Toolbox

Search