# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1194: Only two coins

From New Scientist #2350, 6th July 2002 [link]

Harry, Tom, and I have joined the Apathy Party, which as reported in Colin Singleton‘s puzzle Enigma 1154 proposes to reduce the currency to just two denominations. We each want a currency composed of two coins, each a whole number of pence. We have each suggested which two denominations should be chosen.

We have calculated for each of the three suggestions the largest integral amount that cannot be paid exactly with any combination of the two coins, and also the largest amount that can be paid exactly by only one combination of the two coins.

In each case the answer is a two-digit number. Indeed, the largest integral amount that cannot be paid exactly by any combination of my two denominations is the same as the largest amount that can be paid exactly by only one combination of Harry’s two denominations and also the same as the largest amount that can be paid exactly by only one combination of Tom’s two denominations. (A “combination” need not include both denominations).

Harry’s denominations are different from Tom’s.

Which two denominations have I suggested?

[enigma1194]

### 3 responses to “Enigma 1194: Only two coins”

1. Jim Randell 9 November 2015 at 8:20 am

A bit of analysis (and hand-waving) gives us a quick program.

For positive integers, a and b, with gcd(a, b) = 1, if we consider:

F(a, b, n) = the largest integer, not expressible as a sum of multiples of a and b in n different ways.

Then we know F(a, b, 1) is the Frobenius number of a and b:

F(a, b, 1) = a.b − (a + b)

I claim (without proof – although it seems intuitively reasonable):

F(a, b, n) = n.a.b − (a + b)

This gives rise to the following Python program, which runs in 40ms.

```from collections import defaultdict
from enigma import irange, gcd, printf

# generalised Frobenius numbers
def F(a, b, n=1):
return n * a * b - (a + b)

# record (a, b) pairs by values
f1s = defaultdict(list)
f2s = defaultdict(list)

# consider 1 < a < b < 100
for b in irange(2, 99):
for a in irange(2, b - 1):
if gcd(a, b) > 1: continue
f1 = F(a, b, 1)
f2 = F(a, b, 2)
if not(9 < f1 < f2 < 100): continue
f1s[f1].append((a, b))
f2s[f2].append((a, b))
printf("[a={a} b={b}, F1={f1} F2={f2}]")

# choose my pair from f1s
for (k, Ds) in f1s.items():
# Tom and Harry have the same k in f2s
THs = f2s[k]
if len(THs) > 1:
printf("D = {Ds}, T/H = {THs}")
```

Solution: The setter’s denominations are 3p and 20p.

Tom and Harry’s denominations are (3, 8) and (2, 13) – in some order.

F(3, 20, 1) = F(3, 8, 2) = F(2, 13, 2) = 37

We should also note that F(3, 20, 2) = 97 (the largest value not expressible in 2 different ways for the setter), and F(3, 8, 1) = 13 (the largest value not expressible for Tom/Harry) and F(2, 13, 1) = 11 (the largest value not expressible for Harry/Tom), which are all 2-digit numbers as required.

• Jim Randell 9 November 2015 at 8:26 am

Here’s an alternative program that constructively computes F(a, b, n) (although note that the number passed as the n parameter in this case is one less than that of my previous comment). It also verifies that the computed values match the formula given above. It’s slower than the previous program (it takes 26.7s), but gives the same answer.

```from collections import defaultdict
from enigma import irange, gcd, printf

# count the number of ways to express n as i.a + j.b
# (for non-negative integers i, j)
def express(n, a, b):
t = 0
for jb in irange(0, n, step=b):
(i, r) = divmod(n - jb, a)
if r == 0:
t += 1
return t

# compute generalised Frobenius Numbers of (a, b)
# where a < b and gcd(a, b) = 1
# return a tuple corresponding to ns where each element is the largest
# integer expressible in n different ways, for each n in ns
def F(a, b, *ns):
r = dict((n, None) for n in ns)
xs = list()
x = 0
while True:
x += 1
# look at subsequences of length a + 1
# add in the number of ways of expressing x
xs.append(express(x, a, b))
if len(xs) > a:
x0 = xs[0]
m = min(xs[1:])
if m > x0 and x0 in r:
r[x0] = x - a
if None not in r.values():
assert all(r[n] == (n + 1) * a * b - (a + b) for n in ns)
return tuple(r[n] for n in ns)
xs.pop(0)

# record (a, b) pairs by values
f1s = defaultdict(list)
f2s = defaultdict(list)

# consider 1 < a < b < 100
for b in irange(2, 99):
for a in irange(2, b - 1):
if gcd(a, b) > 1: continue
(f1, f2) = F(a, b, 0, 1)
if not(9 < f1 < f2 < 100): continue
f1s[f1].append((a, b))
f2s[f2].append((a, b))
printf("[a={a} b={b}, F1={f1} F2={f2}]")

# choose my pair from f1s
for (k, Ds) in f1s.items():
# Tom and Harry have the same k in f2s
THs = f2s[k]
if len(THs) > 1:
printf("D = {Ds}, T/H = {THs}")
```
2. Brian Gladman 10 November 2015 at 4:29 pm

Here is a solution using my number theory library:

```from itertools import combinations
from collections import defaultdict

from number_theory import gcd, frobenius_number, frobenius_solve

d1, d2 = defaultdict(list), defaultdict(list)
for a in range(2, 100):
for b in range(a + 1, 100):
if gcd(a, b) == 1:
# calculate the largest amount that cannot be
# made with these two coins
fr = frobenius_number((a, b))
if 10 <= fr < 100:

# calculate the largest amount that can be made
# in only one way
for f in range(150, fr, -1):
fr_sol = list(frobenius_solve((a, b), f))
if len(fr_sol) == 1:
if 10 <= f < 100:
# only (a, b) values that give both amounts
# with two digits need to be considered
d1[fr].append((a, b))
d2[f].append((a, b))
break

# find my first values that are Tom/Harry's second values
for f in sorted(d1.keys() & d2.keys()):
# we need two coin sets for Tom and Harry
if len(d2[f]) > 1:
# my coin set
for m in d1[f]:
# Tom and Harry's coin sets
for t, h in combinations(d2[f], 2):
fs = "Amount {}, Mine {}, <Tom|Harry> <{}|{}>"
print(fs.format(f, m, h, t))
```