Skip to content

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

1212. 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 1111 notes summing to $99. One more note (for example the $100) is needed for $100; a brute-force search confirms 1212 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