This afternoon, Matt Locke tweeted the following problem from his nine-year-old daughter’s maths homework:
Coins in general circulation in the UK come in the denominations 1p, 2p, 5p, 10p, 20p, 50p, £1 and £2, and I think we are supposed to assume that the coins in the problem are drawn from this set.
It’s a curious sort of homework problem, because there is no obvious systematic way to approach it. Presumably the intention is that the child will fiddle about with numbers until they either hit on a solution or give up.
But that is not a very mathematically satisfying approach. It piqued my interest partly because it’s essentially a system of two linear diophantine equations in eight variables. If we let be the number of 1p coins, the number of 2p coins, etc., then we have:
with the additional constraint that precisely five of the eight variables should have non-zero values.
(I have been thinking about systems of linear diophantine equations quite a lot recently, because they play a central role in Lambert’s version of Mayr’s algorithm for Petri net reachability, but that’s another story.)
Now, there are systematic algorithms for finding all the solutions to such a system of equations. If the variables are allowed to take negative values, it is not too hard: the algorithm was first described by Henry J. Stephen Smith in 1861, and the structure he used is nowadays known as the Smith normal form. But if we want only non-negative solutions, as we do here, then it is harder. One algorithm is due to Evelyne Contejean and Hervé Devie in 1994: An Efficient Incremental Algorithm for Solving Systems of Linear Diophantine Equations.
I think Contejean-Devie is roughly as good as any algorithm for this problem, but I’m not an expert. Here are some slides that explain the algorithm pretty clearly. Since all the coefficients are positive, our example has only finitely many solutions and the Contejean-Devie algorithm reduces to a brute-force search.
Another algorithm that would do the job is due to Seymour Ginsburg and Edwin Spanier (1966). Since the set of solutions can be described in Presburger arithmetic, Ginsburg and Spanier’s procedure can extract an explicit finite presentation of this set. But this algorithm is likely to be even slower; it is actually provable – without making any unproven assumptions about complexity classes such as P≠NP – that it must take at least doubly-exponential time in the worst case.
So there isn’t obviously any better way to approach the problem than brute force, and I was intrigued enough with the problem by this point to try a simple-minded attack in Python:
from itertools import combinations COINS = (1, 2, 5, 10, 20, 50, 100, 200) TARGET = 3975 def partitions(n, k): """All the partitions of n into k positive integers. """ if k == 1: yield (n,) return for i in range(1, n): for p in partitions(n-i, k-1): yield (i,) + p def dot(xs, ys): return sum([ x*y for x,y in zip(xs, ys) ]) for coin_values in combinations(COINS, 5): for counts in partitions(100, 5): if dot(coin_values, counts) == TARGET: print tuple(zip(counts, coin_values))
This is literally just systematically checking each of the combinations of 100 coins of five different denominations, and printing out the ones that add up to the right amount.
It turns out that there are 33,798 solutions.
(This last can print all 33,798 solutions in about one second, which is about 90 times faster than the Python equivalent. It’s worth reminding ourselves from time to time just how much processing power we are wasting when we code in inefficient high-level languages like Python, and marvelling at the raw speed and power of modern computers.)
Weird question to ask a nine-year-old, anyway.