Difference between revisions of "Chicken McNugget Theorem"

Revision as of 16:07, 18 February 2010

The Chicken McNugget Theorem 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

Consider the integers $\pmod{m}$ . Let $R = \{0, n, 2n, 3n, 4n ... (m-1)n\}$ . Note that since $m$ and $n$ are relatively prime, $R$ is a Complete residue system in modulo $m$ .

Lemma: For any given residue class $S \pmod{m}$ , call $r$ the member of $R$ in this class. All members greater than or equal to $r$ can be written in the form $am+bn$ while all members less than $r$ cannot for nonnegative $a,b$ .

Proof: Each member of the residue class can be written as $am + r$ for an integer $a$ . Since $r$ is in the form $bn$ , this can be rewritten as $am + bn$ . Nonnegative values of $a$ correspond to members greater than or equal to $r$ . Negative values of $a$ correspond to members less than $r$ . Thus the lemma is proven.

The largest member of $R$ is $(m-1)n$ , so the largest unattainable score $p$ is in the same residue class as $(m-1)n$ .

The largest member of this residue class less than $(m-1)n$ is $(m-1)n - m = mn - m - n$ and the proof is complete.

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 contribues $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 3: / Line 3: @@
 == Origins ==
-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.
+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==

Page

Toolbox

Search