Keep The Change

I’m sorry to have fallen quiet for so long; the week has been a busy one and I haven’t been able to write as much as I want. I did want to point everyone to Geoffrey Brent’s elegant solution of my puzzle about loose change, and whether one could have different types of coin without changing the total number of value of those coins. It’s a wonderful proof and one I can’t see a way to improve on, including an argument for the smallest number of coins that allow this ambiguity. I want to give it some attention.

The proof that there is some ambiguous change amount is a neat sort known as an existence proof, which you likely made it through mathematics class without seeing. In an existence proof one doesn’t particularly care whether one finds a solution to the problem, but instead bothers trying to show whether a solution exists. In mathematics classes for people who aren’t becoming majors, the existence of a solution is nearly guaranteed, except when a problem is poorly proofread (I recall accidentally forcing an introduction-to-multivariable-calculus class to step into elliptic integrals, one of the most viciously difficult fields you can step into without requiring grad school backgrounds), or when the instructor wants to see whether people are just plugging numbers into formulas without understanding them. (I mean the formulas, although the numbers can be a bit iffy too.) (Spoiler alert: they have no idea what the formulas are for, but using them seems to make the instructor happy.)

An existence proof will often give you no idea what the solution is. So for introductory mathematics classes — when it can take some effort to create a problem that doesn’t have a solution, except when you write down a problem confident that it’s fine because you don’t have time to work out the answer before giving it out on the exam — it’s often a poor use of time to bother seeing whether there is some answer; finding the correct solution is, after all, a proof that a correct solution exists. When the questions become more open-ended, less fitting into patterns, then it can be hard to find that correct solution; finding that a solution exists at all then starts being a good use of time.

Knowing there is a solution can be enough, mathematically at least. After all, particularly with a problem like finding sets of coins with the same total number of coins and value, you can if all else fails just keep trying combinations. This is known as “brute force”, and it trusts that if you try enough combinations eventually at least one of them will pan out. As the name suggests it’s more a method of persistance than of cleverness. But once you know that a solution exists, in principle, then you can find it by brute force if nothing else. If you’re doing the problem for fun you have something to scribble around with pencil and paper in an idle moment; if you need the answer you can set a computer to the task. It’ll get an answer someday. It may require longer than your projected lifespan, in which case you might try narrowing the bounds of where a solution might be and look through a smaller part of the universe, but if you’re patient and immortal enough you don’t have to worry about such little implementation troubles.

Also a part of what makes Brent’s proof so appealing to me is that it depends on the pigeon-hole principle: if there are at least twelve coins in the collection, then there are more possible ways to arrange them — more ways to collect pennies, nickels, dimes, and quarters — than there are possible values for them to have. So there must be at least two collections of twelve coins that have the same value. This is beautiful reasoning, obvious once you’ve heard it, and so almost certainly more convincing than nearly any alternatives.

As if that weren’t enough Brent goes on to find the smallest number of coins for which there’s this equal-count, equal-value pairing. That’s also beautifully reasoned, though it requires a little more attention and probably some sitting and thinking about whether that’s reasonable than the existence does. It’s often that way. Showing something has to exist frequently can be easier than proving a particular instance is the optimum (in requiring fewest coins, or smallest amount of money, or whatever other condition is best). It’s still just magnificent, and I don’t see how to top it, and I wanted to give proper attention to the work.