2021 AMC 10 A Fall

Complete problem set with solutions and individual problem pages

Problem 23 Hard

For each positive integer n, let f_{1}(n) be twice the number of positive integer divisors of n, and for j \geq 2, let f_{j}(n)=f_{1}\left(f_{j-1}(n)\right). For how many values of n \leq 50 is f_{50}(n)=12 ?(2021 AMC Fall 10A, Question #23)

  • A.

    7

  • B.

    8

  • C.

    9

  • D.

    10

  • E.

    11

Answer:D

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 p q^{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 p q^{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), \ldots will all be 12 . This is because f_{i+1}(n)=f\left(f_{i}(n)\right) (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^{4} q, or p^{2} q^{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 (D) 10 values (Namely 12,20,28,44,18,45,50,32,36,48 ).

Solution 2:

Observation 1: f_{1}(12)=12. Hence, if n has the property that f_{j}(n)=12 for some j, then f_{k}(n)=12 for all k>j.

Observation 2: f_{1}(8)=8. Hence, if n has the property that f_{j}(n)=8 for some j, then f_{k}(n)=8 for all k>j.

Case 1: n=1 We have f_{1}(n)=2, f_{2}(n)=f_{1}(2)=4, f_{3}(n)=f_{1}(4)=6, f_{4}(n)=f_{1}(6)=8. Hence, Observation 2 implies f_{50}(n)=8.

Case 2:n is prime. We have f_{1}(n)=4, f_{2}(n)=f_{1}(4)=6, f_{3}(n)=f_{1}(6)=8. Hence, Observation 2 implies f_{50}(n)=8.

Case 3 : The prime factorization of n takes the form p_{1}^{2}. We have f_{1}(n)=6, f_{2}(n)=f_{1}(6)=8. Hence, Observation 2 implies f_{50}(n)=8.

Case 4 : The prime factorization of n takes the form p_{1}^{3}. We have f_{1}(n)=8. Hence, Observation 2 implies f_{50}(n)=8.

Case 5 : The prime factorization of n takes the form p_{1}^{4}. We have f_{1}(n)=10, f_{2}(n)=f_{1}(10)=8. Hence, Observation 2 implies f_{50}(n)=8.

Case 6 : The prime factorization of n takes the form p_{1}^{5}. We have f_{1}(n)=12. Hence, Observation 1 implies f_{50}(n)=12. In this case the only n is 2^{5}=32.

Case 7: The prime factorization of n takes the form p_{1} p_{2}. We have f_{1}(n)=8. Hence, Observation 2 implies f_{50}(n)=8.

Case 8 : The prime factorization of n takes the form p_{1} p_{2}^{2}. We have f_{1}(n)=12. Hence, Observation 1 implies f_{50}(n)=12. In this case, all n are 18,50,12,20,45,28,44.

Case 9 : The prime factorization of n takes the form p_{1} p_{2}^{3}. We have f_{1}(n)=16, f_{2}(n)=f_{1}(16)=10, f_{3}(n)=f_{1}(10)=8. Hence, Observation 2 implies f_{50}(n)=8.

Case 10: The prime factorization of n takes the form p_{1} p_{2}^{4}. We have f_{1}(n)=20, f_{2}(n)=f_{1}(20)=12. Hence, Observation 1 implies f_{50}(n)=12. In this case, the only n is 48 .

Case 11: The prime factorization of n takes the form p_{1}^{2} p_{2}^{2}. We have f_{1}(n)=18, f_{2}(n)=f_{1}(18)=12. Hence, Observation 1 implies f_{50}(n)=12. In this case, the only n is 36 .

Case 12: The prime factorization of n takes the form p_{1} p_{2} p_{3}. We have f_{1}(n)=16, f_{2}(n)=f_{1}(16)=10, f_{3}(n)=f_{2}(10)=8. Hence, Observation 2 implies f_{50}(n)=8.

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

Related Problems
Problem 21 2021 AMC 10 A Fall
Problem 22 2021 AMC 10 A Fall
Problem 24 2021 AMC 10 A Fall
Problem 25 2021 AMC 10 A Fall
Think Academy Powered by ChatGPT