Counting coins

This afternoon, Matt Locke tweeted the following problem from his nine-year-old daughter’s maths homework:

3975

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 c_{1} be the number of 1p coins, c_2 the number of 2p coins, etc., then we have:

\begin{aligned}c_1 + 2c_2 + 5c_5 + 10c_{10} + 20c_{20} + 50c_{50} + 100c_{100} + 200c_{200} &= 3975 \\ c_1 + c_2 + c_5 + c_{10} + c_{20} + c_{50} + c_{100} + c_{200} &= 100 \end{aligned}

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 provablewithout 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.

At that point I couldn’t stop, and I implemented first a slightly better algorithm in Python and then a C version of the better algorithm.

(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.

This entry was posted in algorithms, Mathematics. Bookmark the permalink.

14 Responses to Counting coins

  1. Drew DeNardo says:

    33789 or 33798? Which is it?

  2. I can’t help wondering which of those solutions is “correct” in the marking. Are the 9-year-olds taught some method for this sort of problem that would arrive at a particular result?

  3. Also; how does one buy computer software with coins in this day and age? :)

  4. pozorvlak says:

    I agree that this is a strange problem to give a nine-year old, but it’s a standard algorithms problem, discussed in for instance SICP. Keeping a running total of the total value of the coins selected so far lets you bail out of the loop early, greatly shrinking the search space. More at my blog here: http://pozorvlak.livejournal.com/150560.html (read the comments!).

    • Are you sure this is the same problem? I wonder if having a constraint on the number of coins makes it substantially different – but I haven’t thought about it properly, because I am in the middle of Real Work…

      • pozorvlak says:

        I guess it’s a slightly different problem – but the only thing affected is the termination condition of the nested loops, which now becomes “if [remaining total]/[number of coins remaining] is not between [smallest remaining denomination] and [largest remaining denomination], give up and backtrack”.

      • Thanks. So, is the algorithm you’re talking about different from my “improved” one – and if so, how is it different?

      • pozorvlak says:

        Gah! Commented in wrong place. Yes, your improved algorithm looks equivalent to mine.

  5. HTFB says:

    One response on Twitter by @clevergz restates the problem more tractably. “There are five different values of coins” is literally true in the US, with 1c, 5c, 10c, 25c and $1 pieces. (Though he falsely asserts that there is a unique solution).

    In that case I’d expect a good 11-year-old to be able to find an answer by trying successive improvements on a first guess, and a fairly good 15-year-old to be able to present systematically how to do that, and thence how to find a large class of different answers. But only an exceptional 9-year-old would get anywhere just on paper. A smaller problem with actual coins to handle might be interesting at that age.

    You can possibly improve your brute-force algorithm in some cases by considering common factors among subsets of the coins. For UK coinage, for example, I would expect* the Python quickcoin routine to run faster if the coins are enumerated in decreasing order of size. With the enumeration in increasing order, the routine spends a lot of time testing combinations of large coins even though the 1p and 2p pieces don’t add to a multiple of 5p, and so on.

    *OK, I already know it worked, and you found a 10% improvement.

  6. That *is* a crazy homework problem for age 9.

    Here’s an alternative approach. If you care about just one solution rather than all of them, any integer programming library would make quick work of it. You might choose your objective function to minimize the number of coins; then you would use the problem above as your constraints. In this case, the tricky constraint is enforcing that the number of non-zeros is exactly 5, but there are standard ways to do it. (In short, you introduce a set of binary indicator variables for each kind of coin and add a handful of constraints to link them to the main part of the model).

    When I started working with the commercial libraries like CPLEX and Gurobi, I was totally shocked at how effective they were.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s