Difference between revisions of "Chicken McNugget Theorem"
m |
m |
||
Line 61: | Line 61: | ||
Prove that <math>S</math> is the set of all integers. (USAMO) | Prove that <math>S</math> is the set of all integers. (USAMO) | ||
− | |||
==See Also== | ==See Also== |
Revision as of 20:47, 15 February 2016
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
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,
![\[S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.\]](http://latex.artofproblemsolving.com/9/e/3/9e3fcc9c2595bb1f400d5eeda2f8b487a50c4d5c.png)
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 representable in the form
for nonnegative integers
, because
is
and
is the original residue. In addition, each number greater than that permuted residue which is congruent to it
is also representable, because this number is simply the permuted residue summed with some number of
's. The greatest of these residues is
, so every number greater than or equal to it that is congruent to some residue of
(which is any number
) is representable. However, we can assume WLOG that
. This would imply that
. There are
numbers greater than
and less than
, and none of these are congruent to
. Therefore, these numbers are all congruent to some lesser permuted residue, and are thus representable.
If for some positive integers
and
, then we can rearrange to find that
, which implies that
has to be some positive multiple of
. We set
for some positive integer
. With substitution, we can say
, and therefore
and
. However,
is a positive integer. Therefore, we have a contradiction, and
is not representable.
Putting it all together, we can say that for any coprime and
,
is the greatest number not representable in the form
for nonnegative 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)
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)
- 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)