### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,451)
- misc (5)
- project euler (2)
- puzzle (90)
- puzzle# (91)
- site news (65)
- tantalizer (132)
- teaser (7)
- today (1)

### Site Stats

- 266,432 hits

Programming Enigma Puzzles

28 March 2020

Posted by on **From New Scientist #3275, 28th March 2020** [link] [link]

I am about to get on the bus, but I don’t have the exact money for the £1 fare. The driver doesn’t give change so I hand over more than £1 and they keep the excess.

Once I have sat down, I realise that even though I didn’t hand over all my coins, the amount of money I had with me was the largest possible amount I could have had in change without being able to pay £1 (or any multiple of £1) exactly.

How much did I have?

[puzzle#52]

%d bloggers like this:

We can’t use any coin that is a multiple of £1, so the denominations we are left with are: 50p, 20p, 10p, 5p, 2p, 1p. (The 25p crown isn’t in common circulation).

Using a “greedy” strategy we can write down a collection of coins that seems like a reasonable maximum.

I also wrote a program that verifies that this is indeed the maximum possible by exhaustive search:

Run:[ @repl.it ]Solution:You had £1.43.The amount is composed of: 1× 50p, 4× 20p, 1× 5p, 4× 2p.

Although you cannot make £1 exactly you can make £1.01, so you don’t lose out too badly.

The “greedy” strategy it to start with the largest denomination coin, and add as many copies of that coin to the collection of coins, provided that doesn’t mean you can make exactly £1 from the collection. Then move on to the next largest denomination.

Manually we add: 1× 50p, 4× 20p, 0× 10p, 1× 5p, 4× 2p, 0× 1p = 143p.

Here it is as a program:

Out of interest, I tried to look at the numerical data in the Accumulator for Puzzle 52 – but a straight print out had two instances of squeezed text, so not possible easily. In both cases there were 130+ lines of squeezed text which, if expanded, would have stalled the monitor display.

I therefore thought I might add a dictionary to Jim’s 1st posting to see how the number of coin values varied between 101p and 143p.

The code extra lines below made the number of coin distributions clear for the totals:

Jim has pointed out to me that using multiset (after importing it) from Enigma.py library, it

is also possible to look at the number of ways coin totals can occur, again modifying the last part of the 1st posting::

The author of this puzzle is clearly UK-centric, therefore not informing the international readers of the actual denominations that are legal tender. Not knowing the actual denominations, I checked Wikipedia and found that the present legal tender denomination are 1, 2, 5, 20, 25, 50p and 1 and 2 pounds.

The passenger might be carrying one 50, one 25p, 4 20p and 4 2p-coins. That would bring the total to 1.63. Hopefully I do not make a silly mistake.

Funny that by adding a denomination, you make it more difficult to get to the correct amount.

Yes, if you add a 25p coin to the allowable denominations then 163p is the maximum.

The greedy strategy gives you: 1×50p, 1×25p, 4×20p, 4× 2p.

But it can also be made as: 3×25p, 4×20p, 4× 2p.

I live in the UK and can say you never see a 25p crown being used to make purchases. They are special limited edition coins for collectors.

Even though

New Scientistis a UK based magazine, the setter of the puzzle should really have mentioned the denominations we should consider (especially in the International Edition).