AMC 10 · 2016 · #24
Grade 9 number-theoryPick an answer.
Both conditions in this problem are about divisibility, and divisibility is decided prime by prime: the exponent of p in a gcd is the smallest of the four exponents, and in an lcm it is the largest. That makes tool #7 (Identify Subproblems) the engine — one prime becomes one self-contained counting question, and because no condition ever links two different primes, the answers multiply. Tool #9 first strips the common factor 77 so the gcd condition becomes the cleaner 'gcd is 1'. Tool #4 names the exponents so 'gcd' and 'lcm' turn into 'min' and 'max'. Tool #16 counts each prime's quadruples by removing the ones that miss the top value or miss the bottom value instead of building them directly. Then the problem reverses: the count 77,000 is known and the exponents are not, so tool #3 and tool #2 factor 77,000 and rule out every set of exponents but one. Tool #14 finishes by asking which arrangement of those exponents on which primes is smallest.
Divide out the common 77
Dividing out the shared factor simplifies both conditions.
A factor shared by all four numbers rides along untouched through both gcd and lcm, so it can be peeled off at the start and glued back at the end.
6.NS.B.4Solve An Easier Related ProblemLook at one prime at a time
Each prime can be handled alone.
gcd and lcm never mix primes: they just take the smallest and the largest exponent of each prime separately.
Greatest common divisors and least common multiples never mix primes; they act on each prime separately.
▸ Why?
Every number has exactly one prime recipe, so its exponents can be read off prime by prime.
▸ Why?
A common multiple takes the tallest tower of each prime and a common divisor takes the shortest.
One factor of the count per prime
So the count is a product over primes.
When separate decisions never interfere with each other, the number of ways to make them all at once is the product of the number of ways to make each one.
7.SP.C.8Identify SubproblemsCount each prime's quadruples by complement
A complement count gives each factor.
Demanding that a list hits both the top value and the bottom value is easiest to enforce by throwing away the lists that miss one, then repairing the double subtraction.
9.A-SSE.A.2Change Focus Count The ComplementEvery factor is two times odd
Every factor is twice an odd number.
Each prime of N contributes exactly one factor of 2 to the count, so counting the 2s in 77,000 counts the primes of N.
9.A-SSE.A.1Eliminate PossibilitiesPin down the three exponents
That pins the exponents to three values.
Reading a factorization backwards is still just divisor hunting: list the divisors, keep the ones of the right shape, and see which combination fits.
6.NS.B.4Make A Systematic ListMake N as small as possible
The smallest primes go with the biggest exponents.
Repeating a number is expensive, so give the most repetitions to the cheapest prime available.
8.EE.A.1Extreme PrincipleMultiply the 77 back in
Multiplying back gives 27720, choice (A).
The answer has to be checked forwards as well as derived backwards: rebuild the count from the chosen n and confirm it lands on 77,000.
6.EE.A.1Eliminate Possibilitiesgcd and lcm only ever compare exponents one prime at a time, so a count like 77,000 splits into one factor per prime — factor the count and the exponents of the answer fall right out.
- Divide out the common 77
- Look at one prime at a time
- One factor of the count per prime
- Count each prime's quadruples by complement
- Every factor is two times odd
- Pin down the three exponents
- Make N as small as possible
- Multiply the 77 back in