AMC 10 · 2011 · #15
Grade 8 number-theorycountingPick an answer.
The question is a "how many" count, and the count is only trustworthy if the list behind it is exhaustive and repeat-free, so Tool #2 (Make a Systematic List) is the tool that actually produces the answer. It needs raw material first: Tool #7 (Identify Subproblems) splits the eight-digit 2²⁴-1 into pieces small enough to factor, using a difference of squares and then a sum of cubes. Tool #3 (Eliminate Possibilities) then trims the search — the prime 241 is already larger than any two-digit number, so no divisor containing it can qualify. The final sweep is organized by the power of 3, because every divisor has exactly one such description and that uniqueness is what rules out both gaps and double counting.
Reduce to a factoring problem
It is really a factoring problem.
A divisor cannot use ingredients the number does not contain, so the prime factorization settles the whole question.
4.OA.B.4Identify SubproblemsSplit with a difference of squares
A difference of squares does most of the work.
Halving an even exponent rewrites the number as a square minus one, and a square minus one always breaks into two factors.
Halving an even exponent rewrites the number as a square minus one, which always breaks into two factors.
▸ Why?
A difference of two squares is the two quantities added multiplied by the two subtracted.
▸ Why?
A divisor cannot use ingredients the number does not contain, so the prime recipe settles the whole question.
Finish factoring every piece
The last piece splits into two more primes.
A sum of cubes carries its own splitting rule, which cracks the one piece the difference of squares cannot touch.
6.NS.B.2Identify SubproblemsProve 241 is prime
One of them is genuinely prime and too large.
The smaller half of a factor pair can never pass the square root, so six quick divisions settle primality forever.
4.OA.B.4Eliminate PossibilitiesDiscard the oversized prime
Dropping it leaves a much smaller number.
A prime larger than the whole target range cannot hide inside a number that sits in that range.
6.EE.A.1Eliminate PossibilitiesSweep by power of three
Sweeping its divisors gives 12, choice (C).
Unique factorization gives every divisor exactly one address in the list, so an organized sweep meets each one once.
4.OA.B.4Make A Systematic ListBreak the big number down to primes first, then sweep its divisors in a fixed order, so no two-digit factor is missed and none is counted twice.
- Reduce to a factoring problem
- Split with a difference of squares
- Finish factoring every piece
- Prove 241 is prime
- Discard the oversized prime
- Sweep by power of three