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

2021 Fall AMC 10A Problems/Problem 23

Revision as of 09:00, 23 November 2021 by Mc21s (talk | contribs)

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

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

Video Solution by Mathematical Dexterity

https://www.youtube.com/watch?v=WQQVjCdoqWI

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_Fall_AMC_10A_Problems/Problem_23&oldid=165401"