Postage Stamp Problem / Chicken McNugget Theorem

The Frobenius problem (or Chicken McNugget problem) is, given coins worth $a_1, a_2, \ldots, a_n$ units, to find the largest $N$ such that no combination of the coins is worth exactly $N$ units. This value $N = g(a_1,a_2,\ldots,a_n)$ is called the Frobenius number of the $a_i$.

The problem comes up in many real-world contexts, and despite being quite elementary, its general solution is not known. The solution is completely understood for $n = 2$, but even for $n =3$, there is no general closed-form formula for the Frobenius number.

Suppose that a popular fast-food restaurant sells its chicken nuggets in sizes of 6, 9, and 20. Customers who want exactly 21 nuggets can buy two 6-packs and one 9-pack, but customers who want exactly 22 nuggets are out of luck. It may seem somewhat plausible that larger orders will be more likely to be fillable, since there are more potential combinations to try. The Frobenius problem in this case asks for the largest number $g(6,9,20)$ of nuggets that cannot be ordered.

Let $a_1,\ldots,a_n$ be positive integers. Define $$S = \{a_1x_1+\cdots+a_nx_n \colon x_1,\ldots,x_n \text{ nonnegative integers} \}.$$ Note that the nonnegativity of the $x_i$ is what makes the problem interesting; if the $x_i$ are allowed to be arbitrary integers, then $S$ is just the set of multiples of the greatest common divisor of the $a_i,$ by Bezout's identity.

If $a_1= 3$ and $a_2=7$, then $S$ does not contain $11$. Of course $11 = 3\cdot 6 + 7\cdot (-1) = 3\cdot (-1) + 7 \cdot 2,$ but these are not nonnegative integer linear combinations of $3$ and $7$. $($American football fans may recognize $11$ as a fairly rare team score, since the vast majority of points that are scored in a game come in denominations of $3$ and $7.)$

Here are four potential questions, in increasing order of difficulty.

1. Can any sufficiently large positive integer be represented as a nonnegative integer linear combination of the $a_i ?$ $($That is, does the Frobenius number $g(a_1,\ldots,a_n)$ exist?$)$
2. If 1 is true, how large is sufficiently large? (That is, what is the Frobenius number?)
3. If 1 is true, how many integers cannot be represented?
4. Given $N$ and $a_1,\ldots,a_n,$ is there a formula for the number of representations of $N$ as a nonnegative integer linear combination of the $a_i?$

The answers to these questions are all known for $n = 2$, but for $n\ge 3$ only partial answers are known (for 2~4 above).

One necessary condition for question 1 above to hold is that the greatest common divisor of the $a_i$ should be $1$, since if the $a_i$ are all divisible by $d$ then so is any integer linear combination of them. In fact, this condition turns out to be sufficient as well.

If $\text{gcd}(a_1,\ldots,a_n)= 1$, then every sufficiently large positive integer can be represented as a nonnegative integer linear combination of the $a_i$.

If the result is true for $n = 2$, then the general case can be proved inductively. For instance, suppose $g(a_1,a_2)$ exists, and suppose $g\big(g(a_1,a_2)+1,a_3\big)$ exists. Then every sufficiently large positive integer can be written as a nonnegative integer linear combination of $g(a_1,a_2)+1$ and $a_3$. But $g(a_1,a_2)+1$ can be written as a nonnegative integer linear combination of $a_1$ and $a_2$, and substituting that into the original linear combination gives an expression for every sufficiently large positive integer as a nonnegative integer linear combination of $a_1,a_2,a_3$. This technique extends to any value of $n$.

The case $n = 2$ requires a key lemma that answers questions 1 and 2 simultaneously.

Lemma: Suppose $a,b$ are relatively prime. Then $g(a,b) = ab-a-b$.

Proof: First, suppose the number $ab-a-b$ can be written as

$$ab-a-b = ax+by$$

for nonnegative integers $x$ and $y$. Then taking this equation modulo $a$ gives $by \equiv -b \bmod{a}$, implying $y \equiv -1 \bmod{a}$ $($since $\gcd(a,b) = 1,$ $b$ has a multiplicative inverse modulo $a).$ Similarly, $ax \equiv -a \bmod{b}$, implying $x \equiv -1 \bmod{b}.$ Since $x$ and $y$ are nonnegative integers, this gives

$$ax+by \geq a(b-1) + b(a-1) = 2ab - a - b > ab - a - b,$$

a contradiction. So $g(a,b) \ge ab-a-b$.

Now, consider any number $M >ab - a -b.$ By Bézout's Identity, there exist integers $x'$ and $y'$ such that $ax' + by' =1.$ Multiplying both sides by $M$ gives integers $x_0=Mx'$ and $y_0=My'$ such that $ax_0 + by_0 =M.$ A result from the wiki on linear Diophantine equations describes all solutions to the equation $ax+by=M$: $x=x_0 + kb, y= y_0 - ka$ for some integer $k$.

By the division algorithm, we can choose $k$ such that $0 \leq x \leq b-1$. For this value of $k$, $ax + by = M > ab - a - b$ implies $b(y+1) > a(b-1-x).$ Now, since $a,b>0$ and $b-1-x \geq 0,$ this implies $y+1 >0$, or $y \geq 0.$ This gives nonnegative integers $x$ and $y$ such that $ax + by = M.$

This shows that $g(a,b) \le ab-a-b$. So $g(a,b) = ab-a-b$. $_\square$

A shop sells cookies in packages of two sizes, $9$ cookies and $13$ cookies. What is the maximum number of cookies that cannot be expressed as a nonnegative combination of these package sizes?

---

In this problem, $m=13$ and $n = 9$ and $\gcd(13,9) = 1$. By the lemma above, the maximum number of cookies that cannot be expressed as a combination of these sizes is the Frobenius number $$13\times 9-13-9=95.\ _\square$$

In general, there is no polynomial closed formula for $g(a_1, a_2, \ldots a_n)$ for $n > 2$ and, computationally, the Frobenius problem is NP-hard. However, there are polynomial-time algorithms for finding $g(a_1, a_2, \ldots a_n)$ that are exponential in $n$, and there are known upper and lower bounds on the Frobenius number for $n=3$.

Note that the key technique used in the solution to the problem above is this: if there is a run of $a_1$ consecutive representable numbers, then every larger number is also representable, by adding an appropriate multiple of $a_1$ to one of the representations.

(Sylvester, 1882)

If $a$ and $b$ are coprime, exactly half of the integers between $0$ and $g(a,b)$ are representable. So there are $\frac{(a-1)(b-1)}2$ non-representable positive integers.

The second sentence follows from the first (and the lemma above). To see the first, for any integer $0 \leq r \leq g(a,b)$, consider the pair of nonnegative integers $\big(r, g(a,b) - r\big)$. The goal is to show that exactly one of the numbers in this pair is representable.

First, the sum of representable numbers is representable, but $r+\big(g(a,b)-r\big) = g(a,b)$ is not representable. So at most one of the numbers in the pair is representable.

Now, consider any number $0 \leq r \leq g(a,b)$ and suppose $r$ is not representable. Follow the same lines as the proof of the lemma above: by Bézout's Identity, there exist integers $x'$ and $y'$ such that $ax' + by' =1$ and multiplying both sides by $r$ gives integers $x_0=rx'$ and $y_0=ry'$ such that $ax_0 + by_0 =r.$ As above, by linear Diophantine equations, all solutions $(x,y)$ to the equation $ax + by =r$ can be written as $x=x_0 + kb, y= y_0 - ka$ for $k$ an integer. By the division algorithm, we can choose $k$ such that $0 \leq x \leq b-1$. Since $r$ is not representable, for this value of $k$, $y = y_0-ka < 0$. Then

$$\begin{aligned} g(a,b) - r &= ab - a - b - ax - by \\ g(a,b) - r &= a(b-1-x) +b(-y-1), \end{aligned}$$

where $b-1-x \geq 0$ and $-y-1 \geq 0$. Therefore, $g(a,b)-r$ is representable. This shows exactly one of the pair $\big(r, g(a,b) - r\big)$ is representable, as desired. $_\square$

This answers question 3 above (question of which integers cannot be represented) for $n = 2$.

For question 4 above (question of how many representations), there is a beautiful result due to Popoviciu that gives a formula for the number of representations of an integer. The proof uses generating functions and is omitted.

(Popoviciu, 1953)

Let $a$ and $b$ be coprime positive integers, and find integers $a'$ and $b'$ such that $aa' \equiv 1$ mod $b$ and $bb' \equiv 1$ mod $a$. Then the number of representations of a positive integer $n$ as a nonnegative linear combination of $a$ and $b$ is

$$\frac{n}{ab} - \left\{ \frac{b'n}{a} \right\} -\left\{ \frac{a'n}{b} \right\} + 1.$$

Here $\{x\}$ denotes the fractional part of $x$.

In how many ways can $1000$ be represented as a nonnegative integer linear combination of $9$ and $13$?

---

The answer is a little less than $\frac{1000}{9\cdot 13}+1\approx 9.547$. The exact formula requires us to find $a'=3, b' = 7$, and compute

$$\begin{aligned} \frac{1000}{117} - \left\{ \frac{7000}9 \right\} -\left\{ \frac{3000}{13} \right\} + 1 &= \frac{1000}{117} - \frac79 - \frac {10}{13} + 1 \\ &= \frac{1000-91-90+117}{117} \\&= \frac{936}{117} = 8. \end{aligned}$$

In fact, it is not hard to find the representations: $(x,y) = (10,70),(23,61),\ldots,(88,16),(101,7)$. $_\square$