Chicken McNuggets Theorem

I’m going to explain the Chicken McNugget Theorem and its proof in honor of the BTS Chicken McNugget entrée.

We are going to discuss:

1. Where the Chicken McNugget Theorem Originated (hint: the nineteenth century)

2. How the Chicken McNugget Theorem Is Proved

3. How to Interpret the BTS Meal Origin Using the Chicken McNugget Theorem The McNugget Theorem’s narrative McDonald’s used to be the only place in the UK to sell Chicken McNuggets in packs of six, nine, and twenty. Sadly, none of them resembled Jungkook. Naturally, you can purchase two cartons of six McNuggets if you’d like to have twelve. However, it is not feasible to obtain 11 nuggets at once if your options are limited to 6, 9, and 20.
   

The goal of mathematicians was to respond to this query:

What is the maximum quantity of McNuggets that is unavailable in packs of six, nine, or twenty?

Mathematicians poured out their blood, sweat, and tears, and discovered that 43 is the answer. Packs of 6, 9, and 20 nuggets cannot be used to purchase 43 nuggets, but any amount above 43 may be purchased.

The problem, which originated from the Chicken McNugget version, was reportedly first posted on the internet newsgroup rec.puzzles in 1990. It was later republished in Ilan Vardi’s book Computational Recreations in Mathematica in 1991. However, the issue first arose in the late 1800s, long before McDonald’s was even a concept.

Because of the German mathematician Ferdinand Frobenius, the subject is often referred to as the “Frobenius Problem.” Occasionally, he brought up the topic in his speeches. The British mathematician Joseph John Sylvester, who was aware of the problem at least as early as 1882, is typically credited with solving it first.

Before the McNugget variant was developed, people studied the Frobenius subject for approximately a century, developing theorems and formulae around it. Let’s McProve the Chicken McNugget Theorem now that the McNugget version is here.

A Synopsis of Some Modular Arithmetic Materials We need to understand a few concepts from the field of modular arithmetic before we can prove the McNugget theorem. Although this sounds complicated and wide-ranging, all we really need to understand are the notation of modular arithmetic and three ideas: multiplicative inverses, relatively prime integers, and the greatest common divisor.

Note: Dividing 20 by 3 yields 6 and a residual of 2. That remainder can be expressed using modular arithmetic. Should I write this:

20∡2 (mod 3)

That actually means that if you divide 20 by 3, the residue is 2. (We often say that 20 is congruent to 2 mod 3).

An alternative way to put it is this: for any integer k, 20 = 3k+2 if 20≡2 (mod 3). 20 is the product of 3 and the residual of 2. In this case, the equation is true because k=6. Generally speaking:

a = kb + r for some integer k, where a≡r(mod b).

Largest Common Divisor: The largest common divisor, also known as the greatest common factor, is undoubtedly in your memory. The largest integer that divides both a and b is their greatest common divisor. This will be written as gcd(a,b). As an instance, gcd(4,6)=2.

Generally prime numbers: The gcd for a large number of number pairings is 1. For instance, gcd(3,7)=1 because 3 and 7 have no common divisors other than 1. We designate two numbers as comparatively prime or coprime when their gcd is 1.

Multiplicative Inverses: Let us assume, for some integers a, b, and m, that ab≡1(mod m). We say that a and b are multiplicative inverses of each other (mod m) when the product ab equals 1 mod m. Take 10≡3(mod 7) and 5≡5(mod 7) as examples. Mod 7 multiplicative inverses of 10 and 5 are thus 10*5 = 50 and 50≡1(mod 7).

This will be crucial because, to get technical, we know that if a and m are relatively prime, then a multiplicative inverse of a must exist (mod m). 9 and 5, for instance, are comparatively prime. Consequently, we are aware that, mod 5, there exists an integer b such that 9b≡1. It is evident that 9 needs a multiplicative inverse mod 5, and in this instance, that inverse is 4.

The Chicken McNugget Theorem’s Proof

Assume that McDonald’s offers the nuggies in two sizes. These sizes are a and b. Additionally, let’s say that gcd(a,b)=1 because a and b are relatively prime. According to the Chicken McNugget Theorem,

The Chicken McNugget Theorem states that the number M=ab-a-b cannot be expressed as ax+by for any nonnegative integers x and y, for relatively prime positive integers a and b. Additionally, for some nonnegative integers x and y, every number n>M can be expressed as ax+by.

Put differently, you can buy any quantity of McNuggets larger than (ab-a-b), but you cannot combine packets of a- and b-sized McNuggets to buy (ab-a-b) McNuggets. When ax+by=d is achieved through the existence of nonnegative integers x, y, we declare that d is tradable. We will declare d to be unpurchaseable if they don’t exist.

The Chicken McNugget Theorem can be demonstrated using the following two steps:

Show that it is not possible to buy ab-a-b.

Show that there are x,y≥0 such that xa+by=n and that any n>ab-a-b is purchasable. First claim: ab-a-b cannot be bought.

We’re going to apply contradiction as a proof. We start by assuming that the claim is false: that is, that ab-a-b is tradable. It follows that there must be nonnegative integers x and y such that ax+by=ab-a-b if ab-a-b is a buyable pair.

A residual of by is obtained by dividing (ax+by) by a. Thus, mod a, (ax+by)≡by. In the same way, (ab-a-b)≡ -b(mod a). Consequently, by must ≡ -b(mod a) since ax+by=ab-a-b.

Given the relative prime nature of b and an, b’s inverse mod a must be multiplicative. We’ll call this an inverted b. This is what occurs when we multiply both sides of by≡ -b(mod a) by the inverse b’:

b’by-b’-b(mod a)

(y)(b’b)≡ -1(b’b)(mod a)

y ≡ -1 mod a

In a similar vein, we can determine that x≡-1 (mod b) if we divide both sides of the original equation (ax+by=ab-a-b) by b.

Since we said that x and y are nonnegative (you can’t buy “-1 packs” of chicken morsels), we know that they cannot equal -1. Therefore, the lowest value of y is a-1, and the lowest value of x is b-1. Stated differently, x≥b-1 and y≥a-1.

On the other hand, if x≥b-1 and y≥a-1, then the following is true:

Ax + By >= a(b-1) + b(a-1) = ab-a+ab-b = 2ab-a-b is greater than ab-a-b.

According to this, ab-a-b > ab-a-b, which is obviously contradictory. We know that ab-a-b must not be purchasable because its purchasability would result in a contradiction.

Claim 2: You can buy any n > ab-a-b.

Although we already know that ab-a-b is not buyable, we still need to show that it is the largest unbuyable integer.

This evidence is probably going to get more intricate than claim 1. We must first call on the name of a French national who has passed away. That’s right, let’s get to Bézout’s identity:

Bézout’s Identity states that there exist numbers x,y such that ax+by=gcd(a,b) if a and b are integers.

Since gcd(a,b)=1 in this case, there are some integers (x,y) such that ax+by=1. We obtain nax+nby=n by multiplying both sides of the equation by n.

To make our formula a little bit cleaner, let’s define x’=nx and y’=ny: ax’+by’=n. I’m going to accuse you of something else now:

Lemma: (x’-kb, y’+ka) is a solution for any integer k if (x’,y’) is a solution to ax’+by’=n.

A(x’-kb)+b(y’+ka) = ax’-akb+by’+akb = ax’+by’=n is the proof.

In the expression x’-kb, k is the number of multiples of b that we include or exclude from x’. Observe that x’-kb can be precisely determined to lie between 0 and b-1 (0≤ x’-kb ≤b-1). This exact value will be called k’. We will then define x”=x’-k’b and y”=y’+k’a. We can infer that (x”,y”) is a solution to ax+by=n from the lemma. We’re not quite done, though. The nonnegativeness of x” and y” still needs to be confirmed.

By definition, x” is nonnegative because 0≤ x”≤b-1. We must now prove that y” is not negative. We are aware that n>ab-a-b and n=ax”+by”. Combining those results in the following:

ax“+by” > ab-a-b →

by “+b > ab-a-ax” →

b(y”+1) is greater than a(b-1-x”).

Because we know that x”≤b-1, b-1-x”≥0. Since an is positive, a(b-1-x”)≥0, which implies b(y”+1)>0, is also indicated. Since b is positive, y”≥0 since (y”+1)>0. Now that x” and y” have been shown to be nonnegative, it is possible that the number n can be purchased.

The BTS Chicken McNugget Meal was only available from McDonald’s in bundles of ten, according to the Chicken McNugget Theorem. However, suppose McDonald’s decides to rerun the promotion and starts offering a 7-piece meal since, well, BTS has seven members.

Twelve or fifteen nuggets cannot be purchased at once if the BTS Chicken McNugget meal is sold in packs of seven or ten. On the other hand, bundles of 7 and 10 may yield 17 or 21 nuggets. How many BTS nuggets can you not purchase at all?

We have the Chicken McNugget Theorem to address that. The largest amount that cannot be bought is:

ab-a-b = 7 * 10^7 – 10 = 53.

Stated differently, you are able to purchase any quantity exceeding 53 morsels, but not 53 at a time.

Some Additional McNuggets NuggetsThese additional details about the Chicken McNugget Theorem are known to us.

For what reason must a and b be relatively prime? Since there wouldn’t be a limit to the quantity of McNuggets that could be purchased. For instance, chicken McNuggets are sold in the US in packs of four and six (as well as ten and twenty). Given that gcd(4,6)=2, the numbers 4 and 6 are not coprime. It’s easy to notice that McNuggets in containers of four and six cannot be purchased in odd amounts. No maximum amount that cannot be purchased exists.

Generally speaking, you can only purchase n McNuggets if n≡0(mod d) if gcd(a,b)=d. Stated differently, n McNuggets can only be purchased if n is divisible by d. For instance, if gcd(a,b)=5, then no amount that divides by 5 and leaves a residual of 1, 2, 3, or 4 can be purchased (so, a number like 31 would not be buyable since 31≡1(mod 5)).

Essentially, only when a and b are coprime is the Chicken McNugget Theorem interesting.

Instead of two McNugget sizes, how about three? We reviewed the evidence for two distinct sizes of McNuggets, but what about three? In essence, there isn’t a clear formula (and on a sunny spring day in 1990, Frank J. Curtis provided proof of this).

However, there are a number of methods to determine the maximum unpurchaseable amount for three McNugget sizes; the most notable ones are Davison’s (1994), Rødseth’s (1978), and Killingbergtrø’s (2000) algorithms (explained here, as the latter’s original paper was only available in Norwegian).

Is the Theory of Chicken McNuggets useful? Essentially, yes! As you can see from my explanation of sexy primes, the term “sexy prime” has little real-world mathematical significance and is merely a tongue-in-cheek moniker. On the other hand, the Chicken McNugget Theorem is really very useful.

According to Jorge L. Ramírez Alfonsin’s book The Diophantine Frobenius Problem, the issue is related to vector spaces, algebraic geometry, error-correcting codes, and monomial curves—in other words, it’s connected to a number of subjects that mathematicians find essential.

Furthermore, the issue can help us understand Shellsort’s temporal complexity. In essence, Shellsort is a sorting algorithm; however, as of right now, we are unsure of how long the algorithm takes to run. The exact timing remains an unresolved problem. The time it takes for the algorithm can be better understood thanks to the Chicken McNugget Theorem.

In summary

For the time being, the BTS Chicken McNugget entrée is no longer available. The Chicken McNugget Theorem informs us that certain amounts of McNuggets were always unsellable, even though we can only get regularly packaged McNuggets these days, streaming “Butter,” and yearning for a bygone era. We constantly had some Chicken McNuggets left in our McGrasp.

If there’s anything to be learned from this, aside from how to prove the Chicken McNugget Theorem, it’s that mathematics has the ability to expose the true complexity of a situation. even a dish as straightforward and basic as a chicken nugget.

Was this information useful

• yes
• no