AMC 10 · 2003 · #23
Grade 8 number-theoryPick an answer.
Nothing can be counted until N is written in primes, and multiplying nine factorials out is hopeless. Tool #15 (Organize Information in More Ways) fixes that: instead of reading the product factorial by factorial, read it number by number and ask how many of the nine factorials each number 1 through 9 sits inside. That single regrouping turns N into nine simple powers. Tool #7 (Identify Subproblems) then handles the primes one at a time — the exponent of 2, of 3, of 5, of 7 — so a large bookkeeping job becomes four small additions, and later it separates the one hard question ('how many square divisors') into four independent easy ones. Tool #4 (Introduce a Variable) names a general divisor 2^a3^b5^c7^e so that 'divides N' and 'is a perfect square' both become plain conditions on four numbers. Tool #2 (Make a Systematic List) finishes by listing the allowed even exponents for each prime and multiplying the list lengths.
Regroup by base, not by factorial
Regrouping by base, each k appears 10 minus k times across the nine factorials.
Rather than expanding nine long products, ask each small number how many of the factorials it lives inside.
6.EE.A.1Organize Information In More WaysBreak the nine bases into primes
Every base is at most nine, so only the primes 2, 3, 5 and 7 can occur.
Only four primes can hide inside numbers as small as nine, so the whole giant reduces to four exponents.
4.OA.B.4Identify SubproblemsAdd up each prime's exponent
Collecting exponents prime by prime gives 2³⁰ · 3¹³ · 5⁵ · 7³.
Once everything is a power of a prime, the whole product collapses into four running totals.
8.EE.A.1Identify SubproblemsDescribe every divisor
A divisor is any choice of exponents within those bounds, by unique factorization.
A divisor is nothing more than a decision about how much of each prime to keep.
4.OA.B.4Introduce A VariableSay exactly when a divisor is a square
It is a square exactly when every exponent is even, proved in both directions.
Squaring doubles every exponent, so a perfect square is exactly a number whose exponents are all even.
A divisor is a perfect square exactly when every prime in it appears an even number of times.
▸ Why?
Every number breaks into primes in only one way, so squaring simply doubles how many times each prime appears.
▸ Why?
Doubling always lands on an even count, so an odd exponent anywhere is enough to rule a divisor out.
Count the even choices and multiply
The even counts 16, 7, 3 and 2 multiply to 672, choice (B).
Each prime is decided on its own, so the counts of choices multiply.
4.OA.A.3Make A Systematic ListRewrite the product so each number shows how many factorials it lives in, and then a square divisor is just an even helping of each prime.
- Regroup by base, not by factorial
- Break the nine bases into primes
- Add up each prime's exponent
- Describe every divisor
- Say exactly when a divisor is a square
- Count the even choices and multiply