The Nugget Algorithm

Vsalsa! Kevin here, with 45 chicken

nugget

s, 63 cents, and 130 years of

algorithm

ic evolution that means you should wait as little time as possible at the supermarket checkout. Almost. You've been grinding in the mine all day with your pickaxe swinging back and forth... and the only thing you value more than diamonds right now is a box full of sweet chicken

nugget

s and delicious, spicy dipping sauce. . Your mom says she'll give you as many nuggets as you want, but you make things a little difficult for her because she canceled your subscription to Realms. So, you ask her to ask for the most nuggets that, due to the available nugget configurations, are IMPOSSIBLE for her to obtain, which means that her new best friend is the German mathematician Ferdinand Frobenius.

In his late 19th century lectures, Frobenius toyed with a thought experiment that would forever change the way we think about pips. The premise is simple: what is the largest integer that cannot be expressed as a combination of integers with the greatest common divisor of 1? I told you it was simple. The answer is the Frobenius number. Let me explain. Let's say, hypothetically, that pips only come in 5s and 9s. Their greatest common factor is 1. If they only come in groups of 5 or 9, then there are all kinds of orders of small pips that you simply can't form by combining them... like 7, 11 or 16.

You can make a table. of possible combinations, but in 1882, the English mathematician J.J. Sylvester, who was so important in developing the way we think and talk about mathematics that he coined basic terms like “matrix” and “graph,” devised a simple formula for finding the largest number that cannot be formed from two numbers. which 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. It's equal to 31. There's our Frobenius nugget. Because he looks. 32 is possible, that's just (9 + 9 + 9 + 5). So 33 (9 + 9 + 5 + 5 + 5) is equal to 33. That's right 34 (9 + 5 + 5 + 5 + 5 + 5) is equal to 34.

And so is every other number after Frobenius. Having a greatest common factor of 1 is key here, because if the greatest common factor is greater, like 2, there can be no Frobenius number, and the proof for that is in the pips. In the United States, McDonald's only sells nuggets in boxes of 4, 6, 10, and 20. Because the greatest common factor is 2, any odd number (very small or very large) presents an impossible combination to sort. In the United States, you simply cannot order 7 OR 73,212,907 nuggets. No! But as Numberphile's Brady Haran showed in 2012, the nugget situation is more complex in the UK. Since McDonald's in the United Kingdom 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 McDonald's could not. do.

Because look, you can make 42 pips because 6 x 7 = 42. You can make 44 with 20 + 9 + 9 + 6. But no combination of 6, 9, and 20 will give you 43. However, you can make every number after 43. You also cannot make 37, 34, 31, 28 or 25, but 43 is the highest number you cannot make. You can calculate all the possibilities for three values ​​of McNuggets by hand and it doesn't take long. But while there is a formula we used above to find the Frobenius with those two numbers, there is no simple formula for 3 variables, or 4, or 44, or 7218... there is only one

algorithm

that ranges from tedious to requiring a supercomputer. . But who cares about chicken nugget combinations?

Is it really that important to piss off someone at a McDonald's half an hour from Barton in the Beans, or 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 addressed are really about mathematical optimization: what can be done with a given set of numbers, and how easily can it be done? That is the essence of how we use coins and decide their denominations. Under our current systems in places like the US and EU, we are greedy when we make changes.

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 largest denomination of coins to get close to a number without going over, then the next largest, and then the next, until we have the amount we need. In the US, our common currencies are 0.01, 0.05, 0.10, and 0.25. One cent, five cents, ten cents and twenty-five cents. So, to get to $0.63 cents, we would select 2 quarters (0.50), 1 dime (0.10), and 3 pennies (0.03); that is 0.63. It 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 US system of 5/1/10/25, the average number of coins given as change in a transaction was 4.7. But by removing the 10-cent coin and replacing it with an 18-cent coin, Shallit found that optimization increased dramatically, to just 3.89 coins per transaction. Knowing that eliminating a simple coin like the dime would surely not be popular, he then wondered what additional denomination would simplify transactions... and discovered that adding a 0.32 cent coin would reduce the average transaction to 3.46 coins. . For the Canadian system, Shallit's addition of a 0.83 cent coin would reduce the average transaction by about one and a half coins.

But how easily can we even think of the world in terms of 83- or 18-year-olds? And how hard is it not to be greedy? If we had an 18 cent coin, the best way to make change for .54 would be 3 18 bills and not our greedy mentality of 2 quarters and 4 cents. By employing Shallit's optimal denominations, we would halve the number of coins in that transaction, but how natural would that be? Is it possible that being inefficient mathematically can be more efficient in real life? YEAH. If you want to go crazy with me, it is possible to ensure that each exchange transaction between 1 and 100 cents uses no more than 2 coins.

Oh really. You would only need denominations of 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49 and 50; With those, you can change anything. with some combination of only 2 currencies. But, instead of dealing with 4 common types of coins in the US, you would 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 we reverted it for the sake of simplicity. The United States used 2-cent coins between 1864 and 1873, and even had 3-cent coins between 1851 and 1889. Shallit's calculations showed that the presence of a 2 or 3-cent coin reduces the average number of coins in a transaction by 0 ,8.

It turns out that having to calculate in additional denominations is more inconvenient than carrying around a few extra pennies. With fewer types of coins, you won't have to search for specific coins and wait in line at the supermarket checkout. 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, almost everything. The idea was that simple systems could rationalize how we think about the world, and a rough, rounded variation of Renard's “R3” appears in the “1-2-5” monetary system of Europe and China, while the United States 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's not. It's pretty good, but it's not the best possible result in terms of mathematics. It's simply the best possible outcome in terms of people. In most of my videos I like to extract the mathematical beauty hidden in everyday life, but in this one it turned out to be quite the opposite. Perfectly optimal algorithms don't always work well with how our brain works and how we live our lives. There are practical limits to how we can apply our advanced mathematical knowledge to our daily lives, and that's okay.

Because whether it's boxes of chicken nuggets or pockets full of coins, what's best mathematically may not necessarily be what's best for the human experience. Unless you really want 43 chicken nuggets. And as always, thanks for watching.