The McNugget Monoid
How many chicken nuggets can you buy if they are only sold in packs of 6, 9 and 20? The picture shows all the numbers from 0 to 44 that can be made from additive combinations of 6, 9 and 20. All numbers higher than 44 can also be made in this way, which leaves 43 as the largest number of chicken nuggets that could not be bought using packs of these sizes.
The list of numbers in the picture, together with all natural numbers greater than 44, is known as the McNugget monoid. The name derives from the fact that at one point, a well-known fast food company used to sell its chicken nuggets in packs of these sizes.
The McNugget monoid is a typical example of a numerical monoid, which is a subset S of the natural numbers satisfying the following three properties:
(1) the number 0 is an element of S;
(2) S contains all but finitely many natural numbers; and
(3) if x and y are in S, then x + y is in S.
Another way to express condition (2) is to say that S contains all sufficiently large natural numbers. In the case of the McNugget monoid, “sufficently large” means “at least 44”.
We could also have defined the McNugget monoid S as the set of all numbers of the form 6r + 9s + 20t, where r, s and t are nonnegative integers. This is the most efficient way to describe the monoid in this way, and in this context, the set {6, 9, 20} is called the minimal set of generators of S. The numbers 6, 9 and 20 play a special role in S: they are the only strictly positive numbers in S that cannot be written as the sum of two smaller strictly positive numbers from S. Because there are three numbers in the minimal generating set, the McNugget monoid S is said to have an embedding dimension of 3.
Numerical monoids have a long history. They were studied in the late 19th century by the algebraists F.G. Frobenius (1849–1917) and J.J. Sylvester (1814–1897). The largest number that is not an element of a given numerical monoid is called its Frobenius number; for example, the Frobenius number of the McNugget monoid is 43. In the case where the embedding dimension is 2, Sylvester found a simple formula for the Frobenius number of a numerical monoid S in terms of its minimal generators.
The case where the embedding dimension is 3 is provably more complicated. Something that is known about this case is that given any positive integer (such as 43), it is possible to construct a numerical monoid of embedding dimension 3 having that number as its Frobenius number. The minimal generators (such as 6, 9 and 20) for such a monoid will always have the property that no single prime number divides all three of them.
turnnoffyourmind
annaxmalina
germansingergirl
ellievsbear
jacobvanloon
