# Difference between revisions of "Chicken McNugget Theorem"

Anthonyjang (talk | contribs) m |
Mentalgenius (talk | contribs) m (→Proof: -- made the word Bezout internally link to the AoPS Wiki Article) |
||

Line 14: | Line 14: | ||

<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>. | <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>. | ||

− | <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> | + | <i>Proof</i>: By [[Bezout's Lemma]], 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> |

<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}n = N</math>. | <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}n = N</math>. |

## Revision as of 18:21, 12 March 2013

The **Chicken McNugget Theorem** (or **Postage Stamp Problem**) states that for any two relatively prime positive integers , the greatest integer that cannot be written in the form for nonnegative integers is .

A consequence of the theorem is that there are exactly positive integers which cannot be expressed in the form . The proof is based on the fact that in each pair of the form , 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

**Definition**. An integer will be called *purchasable* if there exist nonnegative integers such that .

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

**Lemma**. Let be the set of solutions to . Then for any .

*Proof*: By Bezout's Lemma, there exist integers such that . Then . Hence is nonempty. It is easy to check that for all . We now prove that there are no others. Suppose and are solutions to . Then implies . Since and are coprime and divides , divides and . Similarly . Let be integers such that and . Then implies . We have the desired result.

**Lemma**. For any integer , there exists unique such that .

*Proof*: By the division algorithm, there exists such that .

**Lemma**. is purchasable if and only if .

*Proof*: If , then we may simply pick so is purchasable. If , then if and if , hence at least one coordinate of is negative for all . Thus is not purchasable.

Thus the set of non-purchasable integers is . We would like to find the maximum of this set. Since both are positive, the maximum is achieved when and so that .

## Problems

### Introductory

- Marcy buys paint jars in containers of and . 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 or . What is the largest integer such that there is no way to buy exactly nuggets? Can you Generalize ?(ACOPS)

### Intermediate

- Ninety-four bricks, each measuring are to stacked one on top of another to form a tower 94 bricks tall. Each brick can be oriented so it contributes or or 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 , where and are positive integers. Paint the remaining integer point blue. Find a point on the line such that, for every integer point , the reflection of with respect to is an integer point of a different colour than . (India TST)