The math inside Penny Wise
Play →James Ernest designed this game, and Ben Orlin includes it in Math Games with Bad Drawings. Put a coin down, take back a little less. Making change happens every day, yet it hides real math. Why must the game end? And why are coins 1¢, 5¢, 10¢ and 25¢ anyway?
Secret 1: the game always ends
Each turn you put down one coin and take back less than it is worth. So after every move, the money in all hands together drops by at least 1¢, and the table gains at least 1¢.
With two players there is 128¢ in hand at the start. It drops by at least 1¢ a turn and can never go below zero, so the game cannot last more than 128 turns, however anyone plays.
Mathematicians love this trick: find a quantity that only ever moves one way. If it keeps shrinking and cannot shrink forever, the process has to stop.
Think again: with two players, what is the shortest possible game?
Ready? Check your answer
To be out, you have to put all 10 of your coins down one at a time, so you need at least 10 turns of your own. If the first player never takes anything back, they are out after their 10th coin. The second player has moved 9 times by then, so the shortest game is 10 + 9 = 19 turns.
The same trick settles the two "perfect change" questions. If you must take back exactly 1¢ less, the money in hand drops by exactly 1¢ a turn, so the game still ends. If you may take back as much as you put down, the money in hand need not drop at all: put down a nickel, take the nickel back. The quantity stops moving, and the game can go on forever.
Secret 2: the most coins you can need
Cashiers make change the old way: hand over the biggest coin that still fits, then the next, until the amount is paid. For 68¢ that is 25, 25, 10, 5, 1, 1, 1: seven coins. Always grabbing the biggest piece in sight is called a greedy algorithm.
With 1¢, 5¢, 10¢ and 25¢, the greedy way always uses the fewest coins. So which amount under 99¢ needs the most?
Ready? Check your answer
In the best way to pay, there are at most 4 pennies (five would be a nickel), at most 2 dimes and nickels together (two dimes and a nickel make a quarter), and at most 3 quarters below a dollar. That caps it at 4 + 2 + 3 = 9 coins.
Two amounts need all nine: 94¢ (3 quarters, a dime, a nickel, 4 pennies) and 99¢ (3 quarters, 2 dimes, 4 pennies).
Back in the game: put down a quarter and you may take back up to 24¢, but only if the right change is on the table. The table you leave behind is the next player's chance.
Secret 3: design your own coins
Make every amount from 1¢ to 99¢ with as few coins as possible. With 1, 5, 10 and 25 that takes 470 coins in all, 4.7 per amount.
The mathematician Jeffrey Shallit worked out that with four coins the best choices are 1, 5, 18, 25 or 1, 5, 18, 29: only 389 coins, under 3.9 per amount. His paper was called "What this country needs is an 18¢ piece".
But with an 18¢ coin the greedy way breaks. For 36¢ greedy takes 25, then 5, 5, 1: four coins, when two 18s would do. You save coins, and the cashier has to think harder.
Think again: with 1, 5, 18 and 25, what is the fewest coins for 90¢? How many does greedy use?
Ready? Check your answer
Five 18s make exactly 90¢. Greedy takes three quarters, leaving 15¢, then three nickels: six coins.