PUZZLE IBM-257
Five banknote denominations
IBM Research · Ponder This · 2019-09
IBM Ponder This #257 · September 2019
The US dollar has five common banknote denominations: 1, 5, 10, 20, and 50.
Each integer dollar value between 0 and 99 dollars can be paid in a unique way with a minimal number of notes.
If Alice and Bob each have different amounts of money, they still can have the same set of notes.
For example, if Alice has \92 dollars and Bob has \74 dollars (in a minimal number of notes), they both have the same set of banknotes {1,20,50}.
Let's assume that Alice and Bob have two different random amounts of money uniformly distributed in the [0,99] range with a minimal number of banknotes.
The probability that they have the same set of banknotes is approximately 3.79798%.
Your task, this month, is to find another set of five banknotes such that:
- Each integer dollar value between 0 and 99 dollars can be paid in a unique way with a minimal number of notes; and
- The probability above (same set of banknotes for two different random amounts of money uniformly distributed in the [0,99] range) would be exactly 4%.
Solution
Best opened after a real attemptTo be added.