Chicken Mcnugget Theorem (Dartboard Problem)

Probably, I should begin by explaining what is perhaps the weirdest name for a math theorem in history. Although the problem had been explored by mathematicians like Frobenius and Sylvester in the past, the name is fairly new. In the 1980s, McDonalds used to sell the popular product, 'Chicken McNuggets' in packets of $9$ and $20$. People wondered, what is the largest number of nuggets, that cannot be bought, and came up with the answer of $151$. (Although perhaps its not a very good idea to have $152$ Chicken McNuggets) And thus, we have the name 'Chicken McNugget' Theorem.

The problem, stated in its general form is.. Given two coprime positive integers $a,b$, what is the largest positive integer $f(a,b)$ that is inexpressible as $am+bn$, with nonnegative integers $m,n$ ?

If you answered correctly, congratulations. Otherwise, here's an intuitive explanation of why $f(a,b)$, is close to $ab$. The multiples of $a$, smaller than $ab$, form a complete residue system. Thus, every number $k$ larger than $ab$ must be of the form $am+bn$, where $am < ab$ and $k \equiv am \text{ }(\text{mod }b)$. Also, if $f(a,b)$ is significantly smaller than $ab$, not all residues have been covered, and therefore some numbers are inexpressible.

Actually, it turns out that $f(a,b)$ is explicitly computably and equals $ab-a-b$. We shall now prove this.

Suppose first, that $ax+by = ab-a-b$, for some nonnegative integers $x, y$. Then, $a(x-b+1)=-b(y+1)$. Since $a,b$ are coprime, $a|y+1$ and $b|x-b+1 \implies b|x+1$. So, $y \ge a-1$ and $x \ge b-1$ and therefore, $ab-a-b = ax+by \ge ab-a+ab-b = 2ab-a-b$, which is clearly impossible.

Next we show that any number larger than $ab-a-b$ is expressible. Let $a \ge b$. The numbers $0,a,2a, \cdots ,a(b-2) \le ab-a-b$, cover all residues modulo $b$ except for $a(b-1) \equiv -a \text{ (mod }b\text{)}$.So, every number $>ab-a-b$ that is $\ncong -a \text{ (mod }b\text{)}$. But, the smallest number more than $ab-a-b$, that is $\equiv -a \text{ (mod }b\text{)}$, is $a(b-1)$, which is clearly expressible, and thus all the larger ones are too.

To finish off, I'd like to introduce the generalisation of this problem. Essentially, we ask the same question for $n$ numbers rather than $2$. For $n \ge 3$, no explicit form exists. Although for fixed $n$, there exists a polynomial algorithm (in logarithms of the numbers), in general, the problem is NP-hard. For more information, see Frobenius Coin Problem.

Prove the generalization. Let $a, b$ be natural numbers with $\gcd(a, b) = g$. Then every integer $n\geq\dfrac{(a-g)(b-g)}g$ which is a multiple of $g$ is representable as $ax+by$ for nonnegative $x,y$. The largest non-representable one is $\dfrac{(a-g)(b-g)}g-g$.

IMO 1983, Problem 3

Let $a, b$ and $c$ be positive integers, no two of which have a common divisor greater than $1$. Show that $2abc-ab-bc-ca$ is the largest integer which cannot be expressed in the form $xbc + yca + zab$,where $x, y$ and $z$ are non-negative integers.

(USAMO 2001) Let $S$ be a set of integers, such that

(a) $\exists a,b \in S$ such that $\gcd(a,b) = gcd(a-2,b-2) = 1$.

(b) If $x, y \in S$, then $x^2-y \in S$;

Prove that $S$ is the set of all integers.