Problem 5 · 2005 AMC 8
Easy
Arithmetic & Operations
greedy-packing
Soda is sold in packs of 6, 12 and 24 cans. What is the minimum number of packs needed to buy exactly 90 cans of soda?
Show answer
Answer: B — 5 packs.
Show hints
Hint 1 of 2
Fewest packs means each pack should carry as many cans as possible — so reach for the biggest box first.
Still stuck? Show hint 2 →
Hint 2 of 2
This is the 'greedy' idea: grab the largest unit that still fits, then fill the leftover with the next size down.
Show solution
Approach: greedy — biggest packs first
- Start with the 24-packs: three of them give 72 cans, leaving 90 − 72 = 18 to cover.
- Fill 18 with the next sizes: one 12-pack and one 6-pack.
- Total packs: 3 + 1 + 1 = 5.
- Why greedy is safe here: 6, 12, and 24 each divide the next, so loading up on the biggest box never leaves a remainder you can't fill. (With odd sizes like 5 and 7, greedy can fail — worth remembering.)
Mark:
· log in to save