Problem 4 · AMC 8 Stretch
Core
Number Theory
Arithmetic & Operations
be-greedywork-in-another-base
In the Unlucky Lottery, every prize is a power of 13 dollars — that is \(1\), \(13\), \(169\), \(2{,}197\) dollars, and so on. The total prize money handed out is exactly \(1{,}000{,}000\) dollars. What is the smallest possible number of prizes?
Show answer
Answer: 16 prizes
Show hints
Hint 1 of 4
To use as few prizes as possible, hand out the biggest prizes you can first. List the powers of 13 that are below a million.
Still stuck? Show hint 2 →
Hint 2 of 4
The powers are \(1\), \(13\), \(169\), \(2{,}197\), \(28{,}561\), and \(371{,}293\) dollars. Start by taking as many \(371{,}293\) prizes as fit, then move down to the next size.
Still stuck? Show hint 3 →
Hint 3 of 4
Keep subtracting and moving to the next-smaller power. Add up how many prizes you used in total.
Show solution
Approach: Greedy largest-first, which is exactly base-13 expansion
- To use the fewest prizes, give out the largest prizes first. The powers of 13 up to a million are \(1\), \(13\), \(169\), \(2{,}197\), \(28{,}561\), \(371{,}293\) dollars.
- Two \(371{,}293\) prizes use \(742{,}586\), leaving \(257{,}414\). Nine \(28{,}561\) prizes use \(257{,}049\), leaving \(365\). Zero \(2{,}197\) prizes (too big for \(365\)).
- Two \(169\) prizes use \(338\), leaving \(27\). Two \(13\) prizes use \(26\), leaving \(1\). One \(1\) prize finishes it.
- Total prizes: \(2+9+0+2+2+1=16\).
- Shortcut: this is exactly writing \(1{,}000{,}000\) in base thirteen, namely \(290221_{13}\); the digit sum \(2+9+0+2+2+1=16\) is the minimum number of prizes.
Mark:
· log in to save