Skip to content
the grown-up commonsPlay togetherBack to room

← What the Snack Machine Knows

What the Snack Machine Knows

Three short lessons on the maths inside a snack machine: the one number it remembers, why largest-coin-first change works for coins and not for every token, and how much to stock when nobody knows the demand.

Spark & Whetstone · sparkwhetstone.org/learn/what-the-snack-machine-knows · CC BY-NC-SA 4.0. Answers are at the end, so you can try each question first.

Lesson 1. The machine remembers one number

An exact-change snack machine keeps track of a single thing: how much money has gone in so far. That number is its state. A coin is an input that moves it to the next state, and a coin that would carry it past the price is refused. When the state equals the price, the snack drops.

Drawn out, that is a finite automaton, the first machine in most introductions to computer science. A machine selling a $1.25 snack on quarters has six states: 0, 25, 50, 75, 100 and 125 cents. Change the coins and some states become dead ends. On dimes alone no state can ever reach $1.25, because 125 is not a multiple of 10.

Children meet this on CodeRealm by putting coins into a pretend machine and finding which coins strand them. Adding a nickel fixes every dead end: 5 divides 125 and every gap on the way.

Question. An exact-change machine sells a snack for 90¢ and takes only 20¢ coins. How many of its states can still reach the price?

  1. None of them
  2. Only the last one
  3. All of them

Say it back. In your own words: what is the one thing a snack machine has to remember, and what makes a dead end?

Lesson 2. Largest coin first

When a machine owes you 41¢ it gives a quarter, a dime, a nickel and a penny: the largest coin that fits, then the largest that fits in what is left. For US coins that greedy rule always gives the fewest coins. Mathematicians call such a coin system canonical.

Not every token set is canonical. A machine paying in tokens worth 1, 3 and 4 that owes 6 gives 4 + 1 + 1 by the greedy rule, three tokens, when 3 + 3 is two. The rule that never loses works backwards: the fewest for an amount is one more than the fewest for the amount minus some token, whichever token makes that smallest.

Children on CodeRealm compare the two rules on a table of amounts and find exactly where greed goes wrong.

Question. A machine pays change in tokens worth 1, 4 and 5 and owes you 8. What is the fewest tokens it can give?

  1. 4
  2. 8
  3. 2

Say it back. In your own words: why does largest-coin-first work for coins in your pocket but not for every token set?

Lesson 3. Stocking under uncertainty

A sandwich slot is filled once a week, and nobody knows the week’s demand in advance. Stock too few and a sale is missed; stock too many and a sandwich is thrown away. Each mistake has a price: a missed sale costs the profit it would have made, a wasted sandwich costs what it cost to buy.

The newsvendor rule says: stock enough to cover demand with probability (cost of a miss) ÷ (cost of a miss + cost of waste). If a sandwich costs 75¢ and sells for $1.50 with nothing back for leftovers, the two costs are equal and the aim is a half: stock the middle of the demand range. If leftovers can be sold off for 50¢, waste gets cheaper, the aim rises to three quarters, and the stock goes up.

The same rule sits behind how many papers a newsstand orders, which is where it got its name. LedgerQuest has older children move the salvage value and watch the stock move with it.

Question. Muffins cost 50¢ and sell for $2.00; unsold ones are thrown away. What chance of covering the week’s demand should the stock aim for?

  1. About three quarters
  2. About a half
  3. About a quarter

Say it back. In your own words: what are the two mistakes a stocker can make, and how do their costs set the stock?

At the table: The shoebox machine

Players: Two to four, ages 6 and up. You'll need: A shoebox, a handful of coins, a card for the state, a few wrapped snacks or tokens as the goods.

  1. One player is the machine. Write the price on the box and keep the money-so-far on the card, starting at 0.
  2. The others put in one coin at a time. The machine updates the card, and refuses any coin that would go past the price.
  3. When the card equals the price, hand over the snack and reset the card to 0. Then change the coins the machine takes, and find a price nobody can reach.
  4. Swap who is the machine. Talk about what the card is: the only thing the machine knows.

Answers

  1. None of them — Ninety is not a multiple of twenty, so 0, 20, 40, 60 and 80 are all dead ends. The machine can never vend.
  2. 2 — Four plus four is two tokens. Greedy grabs the five first and is left filling three with ones.
  3. About three quarters — A missed sale loses $1.50 of profit and a wasted muffin loses the 50¢ it cost. 1.50 ÷ (1.50 + 0.50) = 0.75, so the stock sits three quarters of the way up the demand range.