Vsauce! Kevin here, with 45 chicken nuggets, 63 cents and 130 years of algorithmic evolution
that means you wait as little time as possible in the checkout lane at the grocery store.
Almost.
You’ve been grinding in the Mine all day with your pickaxe swinging from side to side…
and the only thing that you value right now more than diamonds is a box full of sweet
chicken nuggets and some delectable, tangy dipping sauce. Your mom says that she’ll
get you as many nuggets as you want, but you to make things a little difficult for her
because she canceled your Realms subscription. So, you ask her to order the largest number
of nuggets that,
due to available nugget configurations, is IMPOSSIBLE for her to get -- which means
that your new best friend is German mathematician Ferdinand Frobenius.
In his late-1800’s lectures, Frobenius toyed with a thought experiment that would change
how we think about nuggets forever. The premise is simple: what’s the largest integer that
cannot be expressed as a combination of integers with the greatest common divisor of 1? Told
ya it was simple. The answer is the Frobenius number.
Let me explain.
Let’s say, hypothetically, that nuggets only come in 5’s and 9’s. Their greatest
common divisor is 1. If they only come in groups of 5’s or 9’s then there are all
sorts of small nugget orders you just can’t make by combining them… like 7, 11, or 16.
You can work out a table of possible combinations, but in 1882, English mathematician J.J. Sylvester,
who was so important to developing how we think and talk about math that he coined basic
terms like “matrix” and “graph,” came up with a simple formula to find the biggest
number you can’t make from two numbers that have a greatest common divisor of 1: (x * y)
- x - y. So, let's just plug in our 5 and our 9. (5 x 9) - 5 - 9. Equals 31. There’s
our nugget Frobenius. Because look. 32 is possible that's just (9 + 9 + 9 + 5). So is
33 (9 + 9 + 5 + 5 + 5) equals 33. So is 34 (9 + 5 + 5 + 5 + 5 + 5) equals 34. And so
is every other number after the Frobenius.
Having a greatest common divisor of 1 is key here, because if the greatest common divisor
is higher, like 2, there can’t be a Frobenius number at all -- and the proof of that is
in the nuggets. In the U.S., McDonald’s only sells nuggets in boxes of 4, 6, 10 and
20. Because the greatest common divisor is 2, any odd number -- very small or very large
-- presents an impossible ordering combination. In America, you just can't order 7 OR 73,212,907
nuggets. No!
But as Brady Haran of Numberphile showed in 2012, the nugget situation is more complex
in the United Kingdom. Since McDonald’s in the U.K. served nuggets in quantities of
6, 9, and 20, Brady was able to stump the cashier with an order of 43 nuggets -- the
highest possible combination of 6, 9, and 20 that the McDonald's couldn’t possibly
make.
Because check it out, you can make 42 nuggets because 6 x 7 = 42. You can make 44 with 20
+ 9 + 9 + 6. But no combination of 6, 9, and 20 will get you 43. However, you can make
every number after 43. You can't make 37, 34, 31, 28, or 25 either but 43 is the highest
number you can’t make.
You can work out all the possibilities for three values of McNuggets by hand and it doesn’t
take too long. But while there is a formula we used earlier to find the Frobenius with
those two numbers, there’s no simple formula for 3 variables, or 4, or 44, or 7,218…
there’s just an algorithm that ranges from tedious to requiring a supercomputer.
But who cares about chicken nugget combinations? Is it really that important to annoy someone
at a McDonald’s half an hour outside of Barton in the Beans, or to get your mom back
for canceling Realms? No -- but it matters to anyone who uses money. Like everyone everywhere
in the world.
The concepts that Frobenius and Sylvester
tackled are really about mathematical optimization:
what can you do with a given set of numbers, and how easily can you do it? That’s at
the heart of how we use coins and decide on their denominations. Under our current systems
in places like the US and the EU, we’re greedy when we make change. Literally.
We use what’s called a Greedy Algorithm to process transactions -- it’s a crude,
common sense way of approaching change. Basically, we select the biggest denomination of coins
to get close to a number without going over, then the next biggest, and then the next,
until we have the amount that we need. In the US our common coins are .01, .05, .10,
and .25. A penny, a nickel, a dime and a quarter. So, to get to $0.63 cents, we’d select 2
quarters (.50), 1 dime (.10), and 3 pennies (.03) --that's 0.63.
That seems like it has to be the best possible way with the best possible numbers. But are
they really optimal denominations?
In 2003, computer scientist Jeffrey Shallit put it to the test. He found that in the 1/5/10/25
American system, the average number of coins given as change in a transaction was 4.7.
But by removing the 10 cent piece and replacing it with an 18 cent piece, Shallit found that
optimization increased markedly -- to just 3.89 coins per transaction.
Knowing that removing a simple coin like the dime surely wouldn’t be popular, he then
wondered what additional denomination would simplify transactions… and he found that
adding a .32 cent piece would reduce the average transaction down to 3.46 coins. For the Canadian
system, Shallit’s addition of an .83 cent piece would reduce the average transaction
by about a coin and a half.
But how easily can we even think about the world in terms of 83’s or 18’s? And how
difficult is it not to be greedy? If we had an 18 cent coin, the best way to make .54
change would be 3 18s and not our go-to greedy mindset of 2 quarters and 4 pennies. By employing
Shallit’s optimal denominations, we’d cut the number of coins in that transaction
by half -- but how natural would it be?
Is it possible that being inefficient mathematically
can be more efficient in real life? YES.
If you want to get wacky with me, it’s possible to ensure that every single change transaction
between 1 and 100 cents uses no more than 2 coins. Seriously. You’d just need denominations
of 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, and 50 -- with those, you
can make change for anything with some combination of just 2 coins. But, instead of dealing with
4 common types of coins in the US, you’d be dealing with 16 that have no obvious rhyme
or reason for their denominations.
We even used to have a more mathematically optimized coin system but rolled it back for
simplicity’s sake. The US used 2 cent pieces between 1864 and 1873, and even had 3 cent
pieces between 1851 and 1889. Shallit’s calculations showed that the presence of a
2 or 3-cent piece reduces the average coins in a transaction by .8. It turns out that
having to calculate with extra denominations is more inconvenient than carrying around
some additional pennies. With fewer coin types you're not fumbling around looking for specific
coins and holding up the checkout line at the grocery store.
It turns out that sometimes what’s best for math isn’t best for everyday life.
In 1870, French military engineer Charles Renard proposed a series of “preferred numbers”
for the world to use with… well, nearly everything. The idea was that simple systems
could streamline how we think about the world, and a rough, rounded variation of Renard’s
“R3” shows up in the “1-2-5” system of currencies in Europe and China, while the
US and Canada use a modified 1-2-5.
Is that heuristic, a basic set of rules to
help us process our numerical world, the mathematically
optimal way to do everything? Well… no, it isn’t. It’s pretty good, but it’s
not the best possible result in terms of math. It’s just the best possible result in terms
of people.
In most of my videos I like to extract the hidden mathematical beauty in everyday life
but for this one it turned out to kinda be the opposite. Perfectly optimal algorithms
don’t always play nicely with how our brains work and how we live our lives. There are
practical limits to how we can apply our advancing mathematical knowledge to our daily lives
-- and that’s okay.
Because whether it's chicken nugget boxes
or pockets full of coins what’s best mathematically
may not necessarily be best for the human experience.
Unless you really, really, really want 43 chicken nuggets.
And as always -- thanks for watching.