Difference between revisions of "Chicken McNugget Theorem"

Revision as of 20:15, 15 February 2016

The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers $m,n$ , the greatest integer that cannot be written in the form $am + bn$ for nonnegative integers $a, b$ is $mn-m-n$ .

A consequence of the theorem is that there are exactly $\frac{(m - 1)(n - 1)}{2}$ positive integers which cannot be expressed in the form $am + bn$ . The proof is based on the fact that in each pair of the form $(k, (m - 1)(n - 1) - k+1)$ , exactly one element is expressible.

Origins

The story goes that the Chicken McNugget Theorem got its name because in McDonalds, people bought Chicken McNuggets in 9 and 20 piece packages. Somebody wondered what the largest amount you could never buy was, assuming that you did not eat or take away any McNuggets. They found the answer to be 151 McNuggets, thus creating the Chicken McNugget Theorem.

Proof 1

Definition. An integer $N \in \mathbb{Z}$ will be called purchasable if there exist nonnegative integers $a,b$ such that $am+bn = N$ .

We would like to prove that $mn-m-n$ is the largest non-purchasable integer. We are required to show that (1) $mn-m-n$ is non-purchasable, and (2) every $N > mn-m-n$ is purchasable. Note that all purchasable integers are nonnegative, thus the set of non-purchasable integers is nonempty.

Lemma. Let $A_{N} \subset \mathbb{Z} \times \mathbb{Z}$ be the set of solutions $(x,y)$ to $xm+yn = N$ . Then $A_{N} = \{(x+kn,y-km) \;:\; k \in \mathbb{Z}\}$ for any $(x,y) \in A_{N}$ .

Proof: By Bezout's Lemma, there exist integers $x',y'$ such that $x'm+y'n = 1$ . Then $(Nx')m+(Ny')n = N$ . Hence $A_{N}$ is nonempty. It is easy to check that $(Nx'+kn,Ny'-km) \in A_{N}$ for all $k \in \mathbb{Z}$ . We now prove that there are no others. Suppose $(x_{1},y_{1})$ and $(x_{2},y_{2})$ are solutions to $xm+yn=N$ . Then $x_{1}m+y_{1}n = x_{2}m+y_{2}n$ implies $m(x_{1}-x_{2}) = n(y_{2}-y_{1})$ . Since $m$ and $n$ are coprime and $m$ divides $n(y_{2}-y_{1})$ , $m$ divides $y_{2}-y_{1}$ and $y_{2} \equiv y_{1} \pmod{m}$ . Similarly $x_{2} \equiv x_{1} \pmod{n}$ . Let $k_{1},k_{2}$ be integers such that $x_{2}-x_{1} = k_{1}n$ and $y_{2}-y_{1} = k_{2}m$ . Then $m(-k_{1}n) = n(k_{2}m)$ implies $k_{1} = -k_{2}.$ We have the desired result. $\square$

Lemma. For any integer $N$ , there exists unique $(a_{N},b_{N}) \in \mathbb{Z} \times \{0,1,\ldots,m-1\}$ such that $a_{N}m + b_{N}n = N$ .

Proof: By the division algorithm, there exists $k$ such that $0 \le y-km \le m-1$ . $\square$

Lemma. $N$ is purchasable if and only if $a_{N} \ge 0$ .

Proof: If $a_{N} \ge 0$ , then we may simply pick $(a,b) = (a_{N},b_{N})$ so $N$ is purchasable. If $a_{N} < 0$ , then $a_{N}+kn < 0$ if $k \le 0$ and $b_{N}-km < 0$ if $k > 0$ , hence at least one coordinate of $(a_{N}+kn,b_{N}-km)$ is negative for all $k \in \mathbb{Z}$ . Thus $N$ is not purchasable. $\square$

Thus the set of non-purchasable integers is $\{xm+yn \;:\; x<0,0 \le y \le m-1\}$ . We would like to find the maximum of this set. Since both $m,n$ are positive, the maximum is achieved when $x = -1$ and $y = m-1$ so that $xm+yn = (-1)m+(m-1)n = mn-m-n$ .

Proof 2

We start with this statement taken from Proof 2 of Fermat's Little Theorem:

"Let $S = \{1,2,3,\cdots, p-1\}$ . Then, we claim that the set $a \cdot S$ , consisting of the product of the elements of $S$ with $a$ , taken modulo $p$ , is simply a permutation of $S$ . In other words,

$S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.$

Clearly none of the $ia$ for $1 \le i \le p-1$ are divisible by $p$ , so it suffices to show that all of the elements in $a \cdot S$ are distinct. Suppose that $ai \equiv aj \pmod{p}$ for $i \neq j$ . Since $\text{gcd}\, (a,p) = 1$ , by the cancellation rule, that reduces to $i \equiv j \pmod{p}$ , which is a contradiction."

Because $m$ and $n$ are coprime, we know that multiplying the residues of $m$ by $n$ simply permutes these residues. Each of these permuted residues is purchasable (using the definition from Proof 1), because $a$ is $0$ and $b$ is the original residue. In addition, each number greater than that permuted residue which is congruent to it $\bmod m$ is also , because this number is simply the permuted residue summed with some number of $m$ 's. The greatest of these residues is $(m-1)n$ , so every number greater than or equal to it that is congruent to some residue of $m$ (which is any number $\geq (m-1)n$ ) is purchasable. However, we can assume WLOG that $m < n$ . This would imply that $(m-2)n < (m-1)n-m$ . There are $m-1$ numbers greater than $(m-1)n-m$ and less than $(m-1)n$ , and none of these are congruent to $(m-1)n \bmod m$ . Therefore, these numbers are all congruent to some lesser permuted residue, and are thus purchasable.

If $(m-1)n-m=am+bn$ for some positive integers $a$ and $b$ , then we can rearrange to find that $(a+1)m=(m-1-b)n$ , which implies that $a+1$ has to be some positive multiple of $n$ . We set $(a+1)=gn$ for some positive integer $g$ . With substitution, we can say $gmn=(m-1-b)n<mn$ , and therefore $gmn<mn$ and $g<1$ . However, $g$ is a positive integer. Therefore, we have a contradiction, and $(m-1)n-m$ is not representable.

Putting it all together, we can say that for any coprime $m$ and $n$ , $mn-m-n$ is the greatest number not representable in the form $am + bn$ for nonnegative integers $a, b$ . $\square$

Generalization

If $m$ and $n$ are not coprime, then we can simply rearrange $am+bn$ into the form $\gcd(m,n) \left( a\frac{m}{\gcd(m,n)}+b\frac{n}{\gcd(m,n)} \right)$ $\frac{m}{\gcd(m,n)}$ and $\frac{n}{\gcd(m,n)}$ are coprime, so we apply Chicken McNugget to find a bound $\frac{mn}{\gcd(m,n)^{2}}-\frac{m}{\gcd(m,n)}-\frac{n}{\gcd(m,n)}$ We can simply multiply $gcd(m,n)$ back into the bound to get $\frac{mn}{\gcd(m,n)}-m-n=\textrm{lcm}(m, n)-m-n$ All positive multiples of $\gcd(m, n)$ greater than this bound are representable in the form $am+bn$ for some positive integers $a, b$ .

Problems

Introductory

Marcy buys paint jars in containers of $2$ and $7$ . What's the largest number of paint jars that Marcy can't obtain?
Bay Area Rapid food sells chicken nuggets. You can buy packages of $11$ or $7$ . What is the largest integer $n$ such that there is no way to buy exactly $n$ nuggets? Can you Generalize ?(ACOPS)

Intermediate

Ninety-four bricks, each measuring $4''\times10''\times19'',$ are to stacked one on top of another to form a tower 94 bricks tall. Each brick can be oriented so it contributes $4''\,$ or $10''\,$ or $19''\,$ to the total height of the tower. How many different tower heights can be achieved using all ninety-four of the bricks? Source

Olympiad

On the real number line, paint red all points that correspond to integers of the form $81x+100y$ , where $x$ and $y$ are positive integers. Paint the remaining integer point blue. Find a point $P$ on the line such that, for every integer point $T$ , the reflection of $T$ with respect to $P$ is an integer point of a different colour than $T$ . (India TST)

Let $S$ be a set of integers (not necessarily positive) such that

(a) there exist $a,b \in S$ with $\gcd(a,b)=\gcd(a-2,b-2)=1$ ;

(b) if $x$ and $y$ are elements of $S$ (possibly equal), then $x^2-y$ also belongs to $S$ .

Prove that $S$ is the set of all integers. (USAMO)

@@ Line 37: / Line 37: @@
 Clearly none of the <math>ia</math> for <math>1 \le i \le p-1</math> are divisible by <math>p</math>, so it suffices to show that all of the elements in <math>a \cdot S</math> are distinct. Suppose that <math>ai \equiv aj \pmod{p}</math> for <math>i \neq j</math>. Since <math>\text{gcd}\, (a,p) = 1</math>, by the cancellation rule, that reduces to <math>i \equiv j \pmod{p}</math>, which is a contradiction."
-Because <math>m</math> and <math>n</math> are coprime, we know that multiplying the residues of <math>m</math> by <math>n</math> simply permutes these residues. Each of these permuted residues is representable in the form <math>am + bn</math> for nonnegative integers <math>a, b</math>, because <math>a</math> is <math>0</math> and <math>b</math> is the original residue. In addition, each number greater than that permuted residue which is congruent to it <math>\bmod m</math> is also representable, because this number is simply the permuted residue summed with some number of <math>m</math>'s. The greatest of these residues is <math>(m-1)n</math>, so every number greater than or equal to it that is congruent to some residue of <math>m</math> (which is any number <math>\geq (m-1)n</math>) is representable. However, we can assume WLOG that <math>m < n</math>. This would imply that <math>(m-2)n < (m-1)n-m</math>. There are <math>m-1</math> numbers greater than <math>(m-1)n-m</math> and less than <math>(m-1)n</math>, and none of these are congruent to <math>(m-1)n \bmod m</math>. Therefore, these numbers are all congruent to some lesser permuted residue, and are thus representable.
+Because <math>m</math> and <math>n</math> are coprime, we know that multiplying the residues of <math>m</math> by <math>n</math> simply permutes these residues. Each of these permuted residues is purchasable (using the definition from Proof 1), because <math>a</math> is <math>0</math> and <math>b</math> is the original residue. In addition, each number greater than that permuted residue which is congruent to it <math>\bmod m</math> is also , because this number is simply the permuted residue summed with some number of <math>m</math>'s. The greatest of these residues is <math>(m-1)n</math>, so every number greater than or equal to it that is congruent to some residue of <math>m</math> (which is any number <math>\geq (m-1)n</math>) is purchasable. However, we can assume WLOG that <math>m < n</math>. This would imply that <math>(m-2)n < (m-1)n-m</math>. There are <math>m-1</math> numbers greater than <math>(m-1)n-m</math> and less than <math>(m-1)n</math>, and none of these are congruent to <math>(m-1)n \bmod m</math>. Therefore, these numbers are all congruent to some lesser permuted residue, and are thus purchasable.
 If <math>(m-1)n-m=am+bn</math> for some positive integers <math>a</math> and <math>b</math>, then we can rearrange to find that <math>(a+1)m=(m-1-b)n</math>, which implies that <math>a+1</math> has to be some positive multiple of <math>n</math>. We set <math>(a+1)=gn</math> for some positive integer <math>g</math>. With substitution, we can say <math>gmn=(m-1-b)n<mn</math>, and therefore <math>gmn<mn</math> and <math>g<1</math>. However, <math>g</math> is a positive integer. Therefore, we have a contradiction, and <math>(m-1)n-m</math> is not representable.
 Putting it all together, we can say that for any coprime <math>m</math> and <math>n</math>, <math>mn-m-n</math> is the greatest number not representable in the form <math>am + bn</math> for nonnegative integers <math>a, b</math>. <math>\square</math>
+==Generalization==
+If <math>m</math> and <math>n</math> are not coprime, then we can simply rearrange <math>am+bn</math> into the form
+<cmath>\gcd(m,n) \left( a\frac{m}{\gcd(m,n)}+b\frac{n}{\gcd(m,n)} \right)</cmath>
+<math>\frac{m}{\gcd(m,n)}</math> and <math>\frac{n}{\gcd(m,n)}</math> are coprime, so we apply Chicken McNugget to find a bound
+<cmath>\frac{mn}{\gcd(m,n)^{2}}-\frac{m}{\gcd(m,n)}-\frac{n}{\gcd(m,n)}</cmath>
+We can simply multiply <math>gcd(m,n)</math> back into the bound to get
+<cmath>\frac{mn}{\gcd(m,n)}-m-n=\textrm{lcm}(m, n)-m-n</cmath>
+All positive multiples of <math>\gcd(m, n)</math> greater than this bound are representable in the form <math>am+bn</math> for some positive integers <math>a, b</math>.
 ==Problems==

Page

Toolbox

Search