Difference between revisions of "Chicken McNugget Theorem"

Revision as of 19:25, 3 August 2011

The Chicken McNugget Theorem (or Postage Stamp 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$ .

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

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, 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 $(x_{2}-x_{1})k_{2}m = (y_{2}-y_{1})k_{1}n$ 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}m = 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 \ge 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$ .

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?

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

@@ Line 6: / Line 6: @@
 ==Proof==
-Consider the integers <math>\pmod{m}</math>. Let <math>R = \{0, n, 2n, 3n, 4n ... (m-1)n\}</math>. Note that since <math>m</math> and <math>n</math> are relatively prime, <math>R</math> is a [[Complete residue system]] in modulo <math>m</math>.
+<b>Definition</b>. An integer <math>N \in \mathbb{Z}</math> will be called <i>purchasable</i> if there exist nonnegative integers <math>a,b</math> such that <math>am+bn = N</math>.
-Lemma:
+We would like to prove that <math>mn-m-n</math> is the largest non-purchasable integer. We are required to show that (1) <math>mn-m-n</math> is non-purchasable, and (2) every <math>N > mn-m-n</math> is purchasable.
-For any given residue class <math>S \pmod{m}</math>, call <math>r</math> the member of <math>R</math> in this class. All members greater than or equal to <math>r</math> can be written in the form <math>am+bn</math> while all members less than <math>r</math> cannot for nonnegative <math>a,b</math>.
+Note that all purchasable integers are nonnegative, thus the set of non-purchasable integers is nonempty.
-Proof:
+<b>Lemma</b>. Let <math>A_{N} \subset \mathbb{Z} \times \mathbb{Z}</math> be the set of solutions <math>(x,y)</math> to <math>xm+yn = N</math>. Then <math>A_{N} = \{(x+kn,y-km) \;:\; k \in \mathbb{Z}\}</math> for any <math>(x,y) \in A_{N}</math>.
-Each member of the residue class can be written as
-<math>am + r</math> for an integer <math>a</math>. Since <math>r</math> is in the form <math>bn</math>, this can be rewritten as <math>am + bn</math>.
-Nonnegative values of <math>a</math> correspond to members greater than or equal to <math>r</math>. Negative values of <math>a</math> correspond to members less than <math>r</math>. Thus the lemma is proven.
-The largest member of <math>R</math> is <math>(m-1)n</math>, so the largest unattainable score <math>p</math> is in the same residue class as <math>(m-1)n</math>.
+<i>Proof</i>: By Bezout, there exist integers <math>x',y'</math> such that <math>x'm+y'n = 1</math>. Then <math>(Nx')m+(Ny')n = N</math>. Hence <math>A_{N}</math> is nonempty. It is easy to check that <math>(Nx'+kn,Ny'-km) \in A_{N}</math> for all <math>k \in \mathbb{Z}</math>. We now prove that there are no others. Suppose <math>(x_{1},y_{1})</math> and <math>(x_{2},y_{2})</math> are solutions to <math>xm+yn=N</math>. Then <math>x_{1}m+y_{1}n = x_{2}m+y_{2}n</math> implies <math>m(x_{1}-x_{2}) = n(y_{2}-y_{1})</math>. Since <math>m</math> and <math>n</math> are coprime and <math>m</math> divides <math>n(y_{2}-y_{1})</math>, <math>m</math> divides <math>y_{2}-y_{1}</math> and <math>y_{2} \equiv y_{1} \pmod{m}</math>. Similarly <math>x_{2} \equiv x_{1} \pmod{n}</math>. Let <math>k_{1},k_{2}</math> be integers such that <math>x_{2}-x_{1} = k_{1}n</math> and <math>y_{2}-y_{1} = k_{2}m</math>. Then <math>(x_{2}-x_{1})k_{2}m = (y_{2}-y_{1})k_{1}n</math> implies <math>k_{1} = k_{2}</math>. We have the desired result. <math>\square</math>
-The largest member of this residue class less than <math>(m-1)n</math> is <math>(m-1)n - m = mn - m - n</math> and the proof is complete.
+<b>Lemma</b>. For any integer <math>N</math>, there exists unique <math>(a_{N},b_{N}) \in \mathbb{Z} \times \{0,1,\ldots,m-1\}</math> such that <math>a_{N}m + b_{N}m = N</math>.
+<i>Proof</i>: By the division algorithm, there exists <math>k</math> such that <math>0 \le y-km \le m-1</math>. <math>\square</math>
+<b>Lemma</b>. <math>N</math> is purchasable if and only if <math>a_{N} \ge 0</math>.
+<i>Proof</i>: If <math>a_{N} \ge 0</math>, then we may simply pick <math>(a,b) = (a_{N},b_{N})</math> so <math>N</math> is purchasable. If <math>a_{N} < 0</math>, then <math>a_{N}+kn < 0</math> if <math>k \ge 0</math> and <math>b_{N}-km < 0</math> if <math>k < 0</math>, hence at least one coordinate of <math>(a_{N}+kn,b_{N}-km)</math> is negative for all <math>k \in \mathbb{Z}</math>. Thus <math>N</math> is not purchasable. <math>\square</math>
+Thus the set of non-purchasable integers is <math>\{xm+yn \;:\; x<0,0 \le y \le m-1\}</math>. We would like to find the maximum of this set.
+Since both <math>m,n</math> are positive, the maximum is achieved when <math>x = -1</math> and <math>y = m-1</math> so that <math>xm+yn = (-1)m+(m-1)n = mn-m-n</math>.
 ==Problems==
@@ Line 36: / Line 42: @@
 {{stub}}
 [[Category:Theorems]]
+[[Category:Number theory]]

Page

Toolbox

Search