43 McNuggets Made Difficult

I mentioned in the last comments thread the McNuggets Problem, and realized belatedly that maybe not everybody knew just what that was. It’s a cute little one, which Wolfram’s Mathworld is able to date to 1991, or maybe 1990. There’s a reference to a March 1990 puzzle on Usenet newsgroup rec.puzzles, but to find it would require some Google-like search engine capable of finding postings on Usenet, and that technology is sadly beyond us.

Whether 1990 or 1991 seems late, since I’m certain the puzzle first appeared about the same time people first saw the original Chicken McNuggets menu options on sale, sometime in the mid-80s. In the original offerings, one could buy a pack of six, nine, or if Mom was feeling particularly flush with cash or you gave a credible impersonation of being willing to share with your siblings, twenty. The obvious question, then, is what’s the largest number of McNuggets which can’t be bought by some combination of these?

This can be studied rigorously, although I don’t know anyone who actually would. It’s more fun to play and see what can be constructed: 12, obviously; 15, as surely; 18 as well (and that by two different patterns, three packs of six or two packs of nine). 21, 24 (again by two paths), 26, 27, 29, 30 … it looks very much like we’re running out of numbers to buy, and some experimentation finds that 43 is the biggest number of McNuggets which can’t be bought. At least, we can find the formulas for 44, 45, 46, 47, 48, and 49, and obviously, any number above that you can get by buying enough six-packs on top of whatever one of those is.

Or, at least, that was the pattern. Some time ago, and I don’t know just when, McDonald’s changed its menu so it sells a four-McNugget pack, a ten, and a twenty. I believe there’s also a children’s McNugget meal, but whether that sells three, four, five, or some other number of McNuggets I don’t know. My casual research into this turned up analyses which still think that the pack sizes are six, nine, and twenty, as well as a McNuggets history brochure from McDonald’s according to which nothing much happened, McNugget-wise, between a Fiesta McNuggets promotion in 1988 giving away a collectible coin and the 2003 switch to all-white meat. It also listed a regional McNuggets Rap commercial, but no valuable data about when the six- and nine-packs were discontinued.

No mathematical problem really stands alone. The McNugget problem has a family of similar problems, called the coin problem. In that form, if your currency is issued in denominations of certain amounts, then, what is the largest amount which can’t be represented? The reasoning involved shouldn’t care whether we have six, nine, and twenty-McNugget boxes and want to know the largest number of McNuggets not purchasable, or a supply of six-, nine-, and twenty-cent pieces and want to know the largest amount which can’t be exactly paid.

But here is the interesting thing. If we have two sizes of boxes — if, say, we could buy McNuggets in nine and twenty-packs — we have a formula to say what the biggest unattainable number is, as long as the sizes haven’t any factors in common. It’s the product of the two sizes, minus each of the two sizes, so, nine times twenty, minus nine, minus twenty, for a total of 151. This formula was discovered in 1884 by James Joseph Sylvester, the first professor of mathematics for Johns Hopkins University and one of the mere mortals of naming mathematical terms. When you briefly learned the quadratic equation you might have run across the name “discriminant” for that term which went under the square root sign, and which said whether the quadratic equation had zero, one, or two roots. The name was bestowed by Sylvester.

If we have three sizes, though, such as with the original McNuggets and their six, nine, and twenty packs, we have an estimate. We can say the biggest number which can’t be reached is at least as big as the square root of three times the sizes, minus each of the sizes. In this case, that would be the square root of three times six times nine times twenty (the square root of 3,240, which is a little under 57), minus six, minus nine, minus twenty (so it must be at least 22). This may not sound like a very good estimate, but we could be worse off.

For example, there might be four sizes. Imagine that McNuggets were sold in packs of six, nine, fourteen, and twenty. We haven’t got any formula to tell us what the biggest unsalable number might be. The general problem — if McNuggets were sold in any of an arbitrarily large collection of packs, what would be the biggest number of un-purchasable McNuggets — is hard, among the hardest set of problems known to humanity. A formula which worked for any arbitrarily big set would be a major breakthrough in mathematics, worthy of fame within the appropriate circles. You haven’t figured it out.

Figuring it out by hand, going through all the numbers, until you find a combination that gives it or that no combination works, is not the breakthrough. But it’s a fine puzzle if you want to keep your addition and memory skills sharp through lunch.