Smallest note collection paying any sum to 100
Question
You may hold any number of $1, $5, $20 and $100 notes. What is the smallest total number of notes such that every whole-dollar amount from $1 to $100 can be paid exactly using some subset of the notes you hold?
Short answer
. Covering every remainder needs four $1 notes, every multiple of 5 below 20 needs three $5 notes, and reaching $99 then needs four $20 notes, for notes summing to $99. One more note (for example the $100) is needed for $100; a brute-force search confirms is minimal.
Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.
See the hint and the full worked solution in the question bank (free account).
Open the worked solution