# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1298: Odd change

From New Scientist #2456, 17th July 2004

I have some coins in my purse whose total value is less than 1 pound sterling. I have tried to make various totals using one or more of these coins and I have discovered two interesting facts.

First, each possible total can only be achieved by one particular combination of denominations. Secondly, the number of different totals possible equals the total value of the coins in pence. If I added any number of 1 pound coins to my purse those two facts would still be true.

Current UK coins with a value less than 1 pound are 50p, 20p, 10p, 5p, 2p, and 1p.

How much money do I have in total in my purse?

Note: I am waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment.

[enigma1298]

### One response to “Enigma 1298: Odd change”

1. Jim Randell 27 August 2014 at 1:30 pm

If there are n combinations and we add a pound coin there are now n combinations (without the pound coin), n combinations (with the pound coin) and the pound coin by itself, so 2n + 1 combinations.

And if the initial amount was p pence, with the addition of the pound coin it is (100 + p) pence.

But these are equal, so:

2x + 1 = 100 + x
⇒ x = 99

So it seems that if the problem has an answer the answer is 99p. We just need to find a combination of denominations of coins that sum to 99p that has has 99 different amounts that can be made in only one way (obviously the combinations will be all the values between 1p and 99p). One simple solution to this is 99× 1p.

This Python 3 program looks for all combinations of coins that sum to 99p in total and can make 99 different combinations. It runs in 284ms.

```from collections import Counter
from itertools import product
from enigma import multiply, irange, printf

T = 99

# coins
coins = (50, 20, 10, 5, 2, 1)

# generate collections of coins to a certain sum
def generate(cs, t, coins):
if t == 0:
yield cs
else:
for (i, x) in enumerate(coins):
if not(x > t):
yield from generate(cs + [x], t - x, coins[i:])

for cs in generate([], T, coins):
# count the different denominations
ds = tuple(Counter(cs).items())
# count the combinations of denominations (exclude the empty set)
t = multiply(n + 1 for (d, n) in ds) - 1
if t != T: continue

# generate the actual combinations
ts = set()
for ns in product(*(irange(0, n) for (d, n) in ds)):
s = sum(d * n for ((d, _), n) in zip(ds, ns))
if s == 0: continue