### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,270)
- misc (3)
- project euler (2)
- puzzle (67)
- site news (50)
- tantalizer (69)
- teaser (7)

### Site Stats

- 206,371 hits

Programming Enigma Puzzles

18 June 2018

Posted by on **From New Scientist #2213, 20th November 1999** [link]

The denominations of coins currently in circulation are 200, 100, 50, 20, 10, 5, 2 and 1p. When we pay for an item we quite often exchange fewer coins when change is given than when the exact amount is offered. For instance, an item costing 91p would require at least four coins (50+20+20+1) for the exact amount, but the purchase can be made with the exchange of only three coins (100+1–10) if change is given.

Harry, Tom and I each bought an identical item that cost less than 100p. None of us offered the exact amount, but we each exchanged fewer coins than if we had done so. In fact, we each exchanged the minimum number of coins possible for an item of that price even though we each offered a different amount of money in payment.

I paid first, and Harry and Tom each included a different one of the coins I had received in my change among the coins that they offered.

How much did the item cost?

[enigma1057]

%d bloggers like this:

I simplified the code by only allowing a single minimal combination of coins for any amount (which is true for the coins and amounts considered by the puzzle).

This Python program runs in 79ms.

Run:[ @repl.it ]Solution:The item cost 83p.The minimum number of coins to pay for the item exactly is 5 (50p + 20p + 10p + 2p + 1p = 83p).

Dick buys the first item, paying with one 100p coin. He receives change of 17p = 10p + 5p + 2p. So 4 coins are exchanged.

Dick gives the 5p coin to Tom, who pays with 2 coins, 100p + 5p = 105p, and receives 20p + 2p = 22p as change. Again 4 coins are exchanged.

Dick gives the 2p coin to Harry, who pays with 3 coins, 100p + 2p + 1p = 103p, and receives one 20p coin as change. Again 4 coins are exchanged.

(Tom and Harry are indistinguishable, so there is also a solution where Dick gives the 5p coin to Harry and the 2p coin to Tom).

If Dick didn’t need to help out Tom and Harry out using his own change it would be possible for the item to cost 84p, 86p or 87p, each of which takes 5 coins to pay for exactly, but Dick, Tom and Harry could each buy an item paying a different amount with a transaction that uses just 4 coins.