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 "2021 Fall AMC 12A Problems/Problem 20"
Line 6: Line 6:
 
<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,20,28,44,18,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>.
 
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,20,28,44,18,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>.
  
Line 12: Line 12:
  
 
~Ericsz
 
~Ericsz
 +
 +
== Solution 2 ==
 +
<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 18, 50, 12, 20, 45, 28, 44.
 +
 +
<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 48.
 +
 +
<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 36.
 +
 +
<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==
 
==Video Solution by Mathematical Dexterity==

Revision as of 20:33, 25 November 2021

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,20,28,44,18,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{D:10}$ values (Namely $12,20,28,44,18,45,50,32,36,48$).

~Ericsz

Solution 2

$\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 18, 50, 12, 20, 45, 28, 44.

$\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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_Fall_AMC_12A_Problems/Problem_20&oldid=166421"