Problem 14 · 2018 AMC 8
Medium
Number Theory
factorizationdigit-sum
Let N be the greatest five-digit number whose digits have a product of 120. What is the sum of the digits of N?
Show answer
Answer: D — 18.
Show hints
Hint 1 of 2
"Greatest number" is decided left to right: a bigger digit in the ten-thousands place beats anything happening later. So your only goal at each step is to make the current leftmost digit as large as possible.
Still stuck? Show hint 2 →
Hint 2 of 2
The technique is a greedy choice: at each slot, grab the biggest single digit (1–9) that still divides what's left of the product, then pass the remaining product to the next slot.
Show solution
Approach: greedy left-to-right factorization
- First digit: the largest digit dividing 120 is 8 (9 doesn't divide 120, since 120/9 isn't whole). Take 8; remaining product 120/8 = 15.
- Second digit: largest digit dividing 15 is 5; remaining 3. Third digit: largest dividing 3 is 3; remaining 1. The last two slots must each be 1 (their product has to be 1).
- So N = 85311, and the digit sum is 8 + 5 + 3 + 1 + 1 = 18.
- Why greedy is safe here: a larger leftmost digit raises the number more than any improvement further right ever could, so locking in the biggest legal digit at each step can't be beaten.
Mark:
· log in to save