Urban Maths: Counting Coins

I have £16.53 in a jar which contains only coins, the change I have been collecting for years. The one or the two pounds coins, or even the 50p are worth much more money and so I am always willing to carry their weight in my pockets and eventually spend them and so, they never make it into the jar. I needed to set up an interesting trivia question for an event organised by Chalkdust (a magazine for the mathematically curious, fully available at www.chalkdustmagazine.com), using my set of coins. I could ask the participants to estimate the number of coins contained in the jar, for instance, or to estimate the amount of money contained in the jar (which is a bit more challenging since smaller coins might be worth more than the larger coins). Using my jar, however, there is a far more interesting question: Given that there are 593 coins, how much money do you think there is in the jar?

Of course, a person could try to guess the amount of money contained in the jar without considering that there are 593 coins, but let’s ignore those answers: knowing the number of coins is a very valuable piece of information! Feasible answers (where feasible means an amount of money that can be obtained with the 593 coins) are between £5.93 (if all the coins were 1p) and £118.60 (if all the coins were 20p). Note that not every amount of money between £5.93 and £118.60 is feasible: for instance, £118.59 is not feasible.

Let $q_{1}$ , $q_{2}$ , $q_{5}$ , $q_{10}$ and $q_{20}$ denote the quantity of 1p, 2p, 5p, 10p and 20p coins in the jar, respectively. The question requires participants to estimate $q_1$ , $q_2$ , $q_5$ , $q_{10}$ and $q_{20}$ , such that $\sum q_i = 593$ . However, two different distributions could result in the same amount of money in the jar. Consider a simple case in which there are only $Q = 5$ coins in the jar. With $Q$ coins, counting the number of different distributions is basically the same problem as counting the number of ways in which a person can place $Q$ balls into 5 distinct boxes, which gives

$\binom{Q+4}{4} = \frac{(Q+4)(Q+3)(Q+2)(Q+1)}{24},$

meaning that a participant could choose between 126 different distributions of the $q_i$ , a number that grows very fast as $Q$ , the number of coins increases. Also, with five coins there are two different combinations which give 9 pence: one 5p coin and four 1p, or alternatively, four 2p coins and one 1p. Although there are 126 different combinations, there are only 71 different feasible totals. Actually, 9p is the smallest amount of money that has two different combinations with the exact same number of coins (five coins).

The example with only five coins, although simple, shows that not every amount of money is feasible but also, there are amounts of money more `likely’ to be correct since there are more distributions which give that answer. For instance, again with the five coins, 4p is not feasible, there is only one distribution which gives 5p, but there are two distributions which give 9p and three distributions which give 18p. Therefore, with five coins, a player has a higher probability of guessing the right answer if they choose 18p instead of choosing, for instance, 9p, 5p or 4p since it is more likely that there is 18p in the jar. In fact, from the many feasible answers, there are 14 of them which are more likely to be right (18p, 24p, 25p, 26p, 27p, 28p, 32p, 33p, 34p, 36p, 37p, 42p, 45p and 52p) since there are three distributions which result in those numbers. Therefore, to the question `How much money do I have in a jar with five coins?’, any of those 14 answers maximise the probability of being correct.

Urban-Maths-Counting-Coins-figure-1 — *Above is the number of combinations which give $M$ pence using only five coins. Below is the number of combinations which give $M$ pence using 8 coins.*

The issue is that the calculations scale too much and too quickly with more coins (Figure1). With eight coins, for instance, there are 495 different distributions, which in total give 128 feasible amounts of money and with eight coins there are three answers (40p, 48p and 55p) which can be obtained with eight different distributions, whereas the rest of the feasible answers are less likely to be obtained.

Back to my jar of coins. What is the probability that selecting the $q_i$ such that $\sum q_i = 593$ , the answer gives £16.53? Now, this is a more interesting and challenging question, as using the same jar with my 593 coins and my £16.53, I need to know in how many ways could I have 1p, 2p, 5p, 10p and 20p coins such that I collect £16.53 and 593 coins? But counting combinations is tricky!

Knowing that I have 593 coins and they make £16.53 I could, for instance, have 55 20p coins, 15 2p coins and the rest (523) 1p coins. But, there are so many combinations! For counting them, note that

$\begin{eqnarray*} \label{FullEquations} q_{1} + q_{2} + q_{5} + q_{10} + q_{20} &=& Q = 593, \\ q_{1} + 2q_{2} + 5q_{5} + 10q_{10} + 20q_{20} &=& M = 1,653, \end{eqnarray*}$

where $Q$ and $M$ are the number of coins and the amount of money, respectively.

We get a couple of equations for $q_1$ and $q_2$ , which then we can turn into restrictions (since negative coins are not a solution)

$\begin{eqnarray*} \label{RestrictionEquations} q_{1} &=& 2Q - M +3 q_{5} + 8q_{10} +18 q_{20} \geq 0, \\ q_{2} &=& M - Q - 4q_{5} -9 q_{10} - 19q_{20} \geq 0. \end{eqnarray*}$

Thus, any integer combination of $q_5$ , $q_{10}$ and $q_{20}\geq 0$ which also satisfy that

$\begin{eqnarray*} 3 q_{5} + 8q_{10} +18 q_{20} &\geq& M - 2Q \text{, and} \\ 4q_{5} -9 q_{10} - 19q_{20} &\leq& M-Q, \end{eqnarray*}$

gives us a distribution with $Q$ coins and $M$ pence. The five restrictions (the two equations and the fact that $q_i\geq 0$ , for $i = 5, 10$ and $20$ ) are the faces of a pentahedron (a polyhedron with five faces). Any point inside or on the faces of the pentahedron and with integer coordinates of $q_5$ , $q_{10}$ and $q_{20}$ also gives integer solutions for $q_1$ and $q_2$ and the set of $q_i$ is such that the two restrictions are satisfied. Thus, any point inside or on the faces of the pentahedron gives a unique combination of coins such that there are 593 coins with £16.53. Every solution to the problem is represented exactly by one of these points, and therefore, for counting the number of combinations, we could also count the number of points with integer coordinates inside the pentahedron (Figure2). Also, if there are no points inside the pentahedron, it means that there are no distributions (or solutions to our problem), for instance, if we want to count the number of ways in which with $Q = 593$ coins we cannot have $M = 592$ pence, since we know that there are, at least £5.93 in the jar.

Urban-Maths-Counting-Coins-figure-2 — The five restrictions can be thought of as the faces of a polyhedron. Any integer combination (any point with integer coordinates) inside the polyhedron gives one unique combination of the coins such that there are $Q = 593$ coins and $M = 1653$ (or £16.53).

We have transformed the problem of measuring the number of combinations into a problem of counting the number of points of a regular grid or lattice inside, or an integer lattice problem. Counting combinations might be tricky, but counting integers inside a polyhedron is slightly easier. There are many integer lattice problems, for instance, the Gauss circle problem is the problem of determining how many integer lattice points there are in a circle centred at the origin and with radius $r$ , which is a more challenging problem than it seems (and I suggest this introductory video https://tinyurl.com/yc46r3gf).

Thinking of the number of combinations as an integer lattice problem allows using some computational power to obtain a solution: there are $261,029$ different combinations with 593 coins which result in £16.53 (the code I used can be found here https://tinyurl.com/y86k2ee3). Since there are $5,239,776,465$ different combinations using 593 coins, then the probability that a person randomly obtains the correct answer is $4.98 \times 10^{-5}$ .

It is also important to notice that my jar contained only £16.53 but it had 593 coins, meaning that each coin had, on average, a value smaller than 3p. If a participant picked any of the feasible answers randomly (values between £5.93 and £118.60) their chances of having the right value of the money contained in my jar would be higher than if they picked a combination at random. The combination of coins I have on my jar was slightly “unexpected”, meaning that it is important also to look at the colour of the coins in the jar: they are mostly copper!

The integer lattice problem also allows constraints to be easily changed, so I could, for instance, have fewer or more coins (so, a smaller or larger $Q$ ) and I could have less or more money (a smaller or larger $M$ ) and use the same technique for counting the number of combinations (Figure 3).

Estimating the number of coins from my jar and being able to map the problem into an integer lattice model gives the power of counting the number of distributions and to visualise it. If I collected other coins in my jar (say, the 50p coin) it could also be mapped into an integer lattice problem, only in a higher dimension and so we would not be able to see the polyhedron of the restrictions.

Urban-Maths-Counting-Coins-figure-3 — *Number of combinations with $Q$ coins on the horizontal axis, which have exactly $M$ pence on the vertical axis.*

If you are mathematically curious, visit Chalkdust, a free magazine designed just for you, produced mainly by postgraduate and undergraduate students from UCL. All of its contents are available on the website www.chalkdustmagazine.com, where you can find our interviews, puzzles and articles for everyone who enjoys maths.