# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1129: Minimal change

From New Scientist #2285, 7th April 2001 [link]

The coins from 1p to 100p in circulation are for 1p, 2p, 5p, 10p, 20p, 50p and 100p. If one receives 40p in change for a purchase it can be paid in a minimum of 2 coins (20p + 20p) but could be paid in one coin more than that minimum number (20p + 10p + 10p). But a few amounts of change cannot be paid for in one coin more than the minimum possible number of coins, for instance 1p and 50p.

Harry, Tom and I each paid 100p for an item priced such that the change due could not be paid in one coin more than the minimum possible number of coins. Each item cost a different amount.

Next day Harry and Tom bought the same items at the same price as on the previous day, whereas I bought a different item at a different price from any of the others, which again was such that the change due from 100p could not be paid in one coin more than the minimum possible number of coins. Each day the total cost of the three purchases was a prime number of pence.

How much did each of my purchases cost?

[enigma1129]

### 2 responses to “Enigma 1129: Minimal change”

1. Jim Randell 6 February 2017 at 8:08 am

This Python program runs in 42ms.

```from itertools import combinations
from enigma import irange, Primes, diff, cached, printf

# can amount <t> be made from <n> coins in <ds>
@cached
def make(t, n, ds):
# amounts we can make from 1 coin
if n == 1: return (t in ds)
# otherwise use a coin less than t
return any(make(t - d, n - 1, ds) for d in ds if d < t)

# denominations to use
denominations = (1, 2, 5, 10, 20, 50, 100)

# consider values less than 100p
vs = list()
for v in irange(1, 99):
# find the minimum number of coins required
for m in irange(1, v):
if make(v, m, denominations):
# record values that can't be done using m + 1 coins
if not make(v, m + 1, denominations):
printf("[{v} -> {m}]")
vs.append(v)
break

printf("[vs = {vs}]")

# possible prices of items
ps = list(100 - v for v in vs)

# primes up to 300
primes = Primes(300)

# choose item amounts for D on the two days (in some order)
for (D1, D2) in combinations(ps, 2):
# choose item amounts for H, T (in some order)
for (H, T) in combinations(diff(ps, [D1, D2]), 2):
# item total on both days is prime
if not(H + T + D1 in primes and H + T + D2 in primes): continue
printf("D1={D1} D2={D2} [H/T={H}/{T}]")
```

Solution: The purchases cost 49p and 95p.

There are only 4 change values (below 100p) that meet the criteria of the puzzle: 1p, 5p, 50p, 51p, 55p.

Harry and Tom’s purchases cost 45p and 99p, so the total cost of the purchases on the two days were 193p and 239p.

2. Brian Gladman 6 February 2017 at 2:49 pm
```from itertools import combinations
from bisect import bisect

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

# simple prime detection up to 360
pr = {2, 3, 5, 7, 11, 13, 17}
def is_prime(x):
return x in pr or x > 18 and all(x % p for p in pr)

# find the minimum number of coins to make <change>
def min_coins(change, coins):
cns = []
while change:
c = coins[bisect(coins, change) - 1]
cns += [c]
change -= c
return cns

# find whether <change> can be made with <n> coins
def make(change, n, coins):
if n == 1:
return change in coins
else:
for c in coins:
if c < change and make(change - c, n - 1, coins):
return True
else:
return False

# find items that can be bought when change cannot be
# provided with one more coin than the minimum possible
item_costs = []
for change in range(1, 100):
nbr = len(min_coins(change, coins))
if not make(change, nbr + 1, coins):
item_costs += [100 - change]

# look for combinations of three items from those identified for
# which their sum is prime
triples = [t for t in combinations(item_costs, 3) if is_prime(sum(t))]

# look for pairs of triples that share two items
for t1, t2 in combinations(triples, 2):
ins = set(t1).intersection(t2)
if len(ins) == 2:
# and extract the items that are not shared
a, b = sorted((*set(t1).difference(ins), *set(t2).difference(ins)))
print('{}p and {}p.'.format(a, b))
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.