AMC 10 · 2021 · #20
Grade 9 number-theoryPick an answer.
Nobody applies a rule 50 times by hand, so the exponent 50 has to be a bluff. Tool #5 (Look for a Pattern) is what calls it: repeated application of a rule on a small set of numbers has to settle into values that repeat, and once a chain reaches a value the rule sends to itself, all remaining steps do nothing. Tool #15 (Organize Information in More Ways) reads the two-line recursive definition as one machine run many times, which is what makes settling visible. Tool #9 (Solve an Easier Related Problem) cuts the work down: one application already forces the chain into ten possible values, so the hard-looking 50-step question becomes a question about ten small numbers. Tool #2 (Make a Systematic List) does the two pieces of bookkeeping — the table of the rule on those ten numbers, and the final enumeration of n by divisor count. Tool #3 (Eliminate Possibilities) throws out every chain that settles on the wrong value. Tool #11 (Work Backwards) then undoes the first step to translate the surviving condition into a plain statement about n.
Name the one repeated rule
Name the one repeated rule.
A recursive definition stacked fifty deep is still just one rule pressed fifty times.
8.F.A.1Organize Information In More WaysBound where the first step lands
The first step shrinks it in one move.
One step collapses fifty possible starting points into ten possible landing spots.
4.OA.B.4Solve An Easier Related ProblemFind the values that stick
Find the values that stick.
If the machine hands back exactly what you gave it, running it forever changes nothing.
9.F-IF.A.2Look For A PatternTabulate the rule on ten numbers
Tabulate the rule on ten numbers.
Ten short divisor counts decide the fate of every chain in the problem.
4.OA.C.5Make A Systematic ListTrace each chain to its home
Trace each chain to its home.
Only two resting values exist, so each start just has to be sorted into the right one.
9.F-IF.A.3Eliminate PossibilitiesWork backwards to divisor counts
Work backwards to divisor counts.
The fifty-step condition was a costume worn by one plain fact about n alone.
6.EE.B.5Work BackwardsCount the numbers with six divisors
Count the numbers with six divisors.
The divisor count depends only on the exponents, so the search is over shapes of factorizations, not over numbers.
The divisor count depends only on the exponents, so the search is over shapes of factorizations.
▸ Why?
Every number has exactly one prime recipe, so a divisor is nothing but a choice of exponents.
▸ Why?
Those choices are made independently for each prime, so the count is a product of the exponents plus one.
Count nine and ten, then total
Adding them all gives 10.
High exponents shoot past 50 almost immediately, so only a couple of factorization shapes survive the size limit.
4.OA.B.4Make A Systematic ListDoubling the divisor count sends every start below 51 into a chain that parks on either 8 or 12 within three steps, so the fifty-step question is really just "which n ≤ 50 have exactly 6, 9, or 10 divisors?" — and there are 10 of them.
- Name the one repeated rule
- Bound where the first step lands
- Find the values that stick
- Tabulate the rule on ten numbers
- Trace each chain to its home
- Work backwards to divisor counts
- Count the numbers with six divisors
- Count nine and ten, then total