Chicken McNugget Theorem
The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin 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.
Contents
[hide]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 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 .
Proof 2
We start with this statement taken from Proof 2 of Fermat's Little Theorem:
"Let . Then, we claim that the set , consisting of the product of the elements of with , taken modulo , is simply a permutation of . In other words,
Clearly none of the for are divisible by , so it suffices to show that all of the elements in are distinct. Suppose that for . Since , by the cancellation rule, that reduces to , which is a contradiction."
Because and are coprime, we know that multiplying the residues of by simply permutes these residues. Each of these permuted residues is purchasable (using the definition from Proof 1), because, in the form , is and is the original residue. We now prove the following lemma.
Lemma: For any nonnegative integer , is the least purchasable number .
Proof: Any number that is less than and congruent to it can be represented in the form , where is a positive integer. If this is purchasable, we can say for some nonnegative integers . This can be rearranged into , which implies that is a multiple of (since ). We can say that for some positive integer , and substitute to get . Because , , and . We divide by to get . However, we defined to be a positive integer, and all positive integers are greater than or equal to . Therefore, we have a contradiction, and is the least purchasable number congruent to .
This means that because is purchasable, every number that is greater than and congruent to it is also purchasable (because these numbers are in the form where ). Another result of this Lemma is that is the greatest number that is not purchasable. , so , which shows that is the greatest number in the form . Any number greater than this and congruent to some is purchasable, because that number is greater than . All numbers are congruent to some , and thus all numbers greater than are purchasable.
Putting it all together, we can say that for any coprime and , is the greatest number not representable in the form for nonnegative integers .
Corollary
This corollary is based off of Proof 2, so it is necessary to read that proof before this corollary. We prove the following lemma.
Lemma For any integer , exactly one of the integers , is not purchasable.
Proof: Because every number is congruent to some residue of permuted by , we can set for some . We can break this into two cases.
Case 1: . This implies that is not purchasable, and that . is a permuted residue, and a result of the lemma in Proof 2 was that a permuted residue is the least number congruent to itself that is purchasable. Therefore, and , so is purchasable.
Case 2: . This implies that is purchasable, and that . Again, because is the least number congruent to itself that is purchasable, and because and , is not purchasable.
We now limit the values of to all integers , which limits the values of to . Because and are coprime, only one of them can be a multiple of . Therefore, , showing that is not an integer and that and are integers. We can now set limits that are equivalent to the previous on the values of and so that they cover all integers form to without overlap: and . There are values of , and each is paired with a value of , so we can make different ordered pairs of the form . The coordinates of these ordered pairs cover all integers from to inclusive, and each contains exactly one not-purchasable integer, so that means that there are different not-purchasable integers from to . All integers greater than are purchasable, so that means there are a total of integers that are not purchasable.
In other words, for every pair of coprime integers , there are exactly nonnegative integers that cannot be represented in the form for nonnegative integers .
Generalization
If and are not coprime, then we can simply rearrange into the form and are coprime, so we apply Chicken McNugget to find a bound We can simply multiply back into the bound to get Therefore, all multiples of greater than are representable in the form for some positive integers .
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)
- If a game of American Football has only scores of field goals (3 points) and touchdowns with the extra point (7 points), then what is the greatest score that cannot be the score of a team in this football game (ignoring time constraints)?
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? AIME
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)
- Let be a set of integers (not necessarily positive) such that
(a) there exist with ;
(b) if and are elements of (possibly equal), then also belongs to .
Prove that is the set of all integers. (USAMO)