Cash and Envelopes
Alice wants to buy Bob’s painting, knowing only that it costs no more than $100,000 and that the price will be an exact dollar figure (e.g. not $13.35).
Bob insists that he only accepts cash, so Alice goes out to the bank and collects $100,000. As Alice doesn’t want to risk getting mugged, she devises a plan:
She places her money in 17 sealed envelopes, numbered accordingly (i.e. they increase in value). The banknotes are distributed in such a way that no matter what price Bob asks, Alice can pay Bob exactly without having to open an envelope.
It is assumed that each envelope contains the least possible number of bills available in US currency (e.g. a fifty-dollar-bill instead of 5 ten-dollar-bills).
When Alice meets Bob, she is told that the painting costs $31721. She pays with 11 envelopes.
With how many one-dollar-bills must Alice pay?
(Remember the US Dollar Bills are $1, $2, $5, $10, $20, $50, $100)