# Enigmatic Code

Programming Enigma Puzzles

## Puzzle #10: Betty’s change

From New Scientist #3237, 6th July 2019 [link] [link]

Betty works at a cash register in the US. When you purchase something from her, Betty always gives you your change the sensible way: by selecting the largest coins that don’t take her over the amount that she owes you. For example, if she owed you 37 cents, she would first pick out a quarter (25 cents), then a dime (10 cents) then two pennies (a cent each).

However, this morning she has run out of nickels (5 cents) to give out as change, though she has plenty of pennies, dimes and quarters. When she gives you your change, you notice that she has given you twice as many coins as she could have done if she hadn’t been so keen to always start with the largest coin. What is the smallest possible monetary value of the change she has given you?

[puzzle#10]

### One response to “Puzzle #10: Betty’s change”

1. Jim Randell 6 July 2019 at 8:30 am

My first thought was to look for an amount a bit greater than 25¢ that can easily be expressed using other coins. 30¢ is the first obvious candidate, which can be expressed using 3× 10¢ coins. And without any 5¢ coins Betty would give the change as 25¢ + 5× 1¢ = 6 coins.

This Python program demonstrates that this is the smallest possible amount. It runs in 99ms.

Run: [ @repl.it ]

```from enigma import irange, inf, div, first, printf

# greedy algorithm
def greedy(t, ds):
s = list()
for d in ds:
n = t // d
s.append(n)
t -= d * n
return (s if t == 0 else None)

# simple algorithm (from denominations.py)
def express(t, ds, s=[]):
if t == 0:
if not(ds):
yield s
else:
yield s + [0] * len(ds)
elif ds:
d = ds[0]
for i in irange(0, t // d):
yield from express(t - d * i, ds[1:], s + [i])

# solve the puzzle using the specified denominations
def solve(ds):

# consider total amount
for t in irange(1, inf):
# using the greedy algorithm
g = greedy(t, ds)
n = sum(g)

# can we express t using half as many coins?
k = div(n, 2)
if k is None: continue
for s in express(t, ds):
if sum(s) == k:
printf("t={t} using {ds}: greedy={g}, simple={s}")
return

# available denominations of coin
solve([25, 10, 1])
```

Solution: The smallest amount of change is 30¢.

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