Algebra in the City All articles
Consumer Maths

The Equation in Your Pocket: Why the Staff-Room Vending Machine Won't Take Your Exact Change

Algebra in the City
The Equation in Your Pocket: Why the Staff-Room Vending Machine Won't Take Your Exact Change

Photo: JThomas , CC BY-SA 2.0, via Wikimedia Commons

At 3.17 on a Tuesday afternoon, the staff-room vending machine is doing what it does best: refusing perfectly good money. The flap says EXACT CHANGE ONLY. The price of the thing you want — a suspiciously small flapjack — is £1.20. You have a pocket full of 20p and 50p coins. You feed in six 20ps and it works. Another day you feed in one 20p and two 50ps and it also works. Both are exact. So why does the machine sometimes flash its red light at a pile that looks, to the naked eye, like £1.20?

The equation in your hand

Let a be the number of 20p coins and b the number of 50p coins. In pence, the machine is asking for

20a + 50b = 120.

This is a linear Diophantine equation: an equation with whole-number solutions. Divide everything by 10 and it becomes 2a + 5b = 12. The non-negative solutions are (a, b) = (6, 0) and (1, 2). Six 20ps, or one 20p plus two 50ps. The machine does not care about the shape of the pile; it cares whether the equation has a solution using the coins you actually have.

The gcd is the bouncer

For a price p, the left-hand side of 20a + 50b is always a multiple of 10. So no arrangement of 20p and 50p coins can make £1.15, because 115 is not divisible by 10. The greatest common divisor of 20 and 50 is 10, and that gcd acts like a bouncer: it filters out every price that is not a multiple of 10p.

But being divisible by 10 is not enough. Try 30p. The equation 20a + 50b = 30 has no non-negative whole-number solution. You cannot make 30p from 20p and 50p coins. The largest impossible multiple of 10p with this pair is 30p; every multiple of 10p from 40p upwards can be made. There is a formula for this coin problem, usually named after Frobenius: for two coin values with gcd d, the largest impossible multiple of d is (20 × 50)/10 − 20 − 50 = 30p. Add a 5p coin to the mix and the picture changes again: with 5p, 20p and 50p you can make every multiple of 5p, because the 5p coin handles the odd jobs.

Your pocket is the real coin system

The machine may accept 5p, 10p, 20p, 50p, £1 and £2 coins. Your pocket carries some subset of that. If you have only £1 and £2 coins, £1.20 is impossible. If you have only 20p and 50p coins, it is possible in two ways. Two people standing at the same machine can face different algebra because their coin sets are different.

That is why exact-change machines feel personal. They are not testing whether you have enough money in total. They are testing whether your particular multiset of coins solves an integer equation.

A napkin method

Write the price in pence. Write your coin values as coefficients. Divide through by their gcd. Then look for whole-number solutions.

For £1.20 with 20p and 50p coins, divide by 10 to get 2a + 5b = 12. Since 2a is even, 5b must be even, so b must be even. Try b = 0: a = 6. Try b = 2: a = 1. Try b = 4: a would be negative. So there are exactly two non-negative solutions. For £1.30, 2a + 5b = 13 gives b = 1 and a = 4, so one 50p and four 20ps work. For £1.15 the gcd stops you before you start.

If the equation has no non-negative solution, the machine wins. If it has one, you still have to feed the coins in before the bus comes.

Why exact change matters

If the machine gave change, you would only need an inequality: your coins would have to be worth at least £1.20. Exact change turns that inequality into an equality. The machine is not being awkward for the sake of it; it is asking for a whole-number solution to a linear equation. That is a small piece of number theory with a flapjack habit.

Next time the red light flashes, resist the urge to shake the machine. Write the equation on a napkin, check the gcd, and see whether your pocket contains a solution. The staff-room vending machine is not just a snack dispenser. It is a Diophantine equation with a coin slot.

All Articles

Related Articles

The Straight Line to the Green Box: Working Out What Your Broadband Can Actually Do

The Straight Line to the Green Box: Working Out What Your Broadband Can Actually Do

The Lid and the Cliff: What Your Library Slip Is Really Counting

The Lid and the Cliff: What Your Library Slip Is Really Counting

Two Lines, One Meter: The Break-Even Point Hiding in Your Energy Tariff

Two Lines, One Meter: The Break-Even Point Hiding in Your Energy Tariff