Difference between revisions of "Chicken McNugget Theorem"
(→Origins) |
m |
||
Line 1: | Line 1: | ||
− | The '''Chicken McNugget Theorem''' states that for any two [[relatively prime]] [[positive integer]]s <math>m,n</math>, the greatest integer that cannot be written in the form <math>am + bn</math> for [[nonnegative]] integers <math>a, b</math> is <math>mn-m-n</math>. | + | The '''Chicken McNugget Theorem''' (or '''Postage Stamp Problem''') states that for any two [[relatively prime]] [[positive integer]]s <math>m,n</math>, the greatest integer that cannot be written in the form <math>am + bn</math> for [[nonnegative]] integers <math>a, b</math> is <math>mn-m-n</math>. |
Line 25: | Line 25: | ||
===Intermediate=== | ===Intermediate=== | ||
− | Ninety-four bricks, each measuring <math>4''\times10''\times19'',</math> are to stacked one on top of another to form a tower 94 bricks tall. Each brick can be oriented so it | + | Ninety-four bricks, each measuring <math>4''\times10''\times19'',</math> are to stacked one on top of another to form a tower 94 bricks tall. Each brick can be oriented so it contributes <math>4''\,</math> or <math>10''\,</math> or <math>19''\,</math> to the total height of the tower. How many different tower heights can be achieved using all ninety-four of the bricks? [[1994 AIME Problems/Problem 11|Source]] |
===Olympiad=== | ===Olympiad=== |
Revision as of 17:57, 3 August 2011
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
.
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 . Let
. Note that since
and
are relatively prime,
is a Complete residue system in modulo
.
Lemma:
For any given residue class , call
the member of
in this class. All members greater than or equal to
can be written in the form
while all members less than
cannot for nonnegative
.
Proof:
Each member of the residue class can be written as
for an integer
. Since
is in the form
, this can be rewritten as
.
Nonnegative values of
correspond to members greater than or equal to
. Negative values of
correspond to members less than
. Thus the lemma is proven.
The largest member of is
, so the largest unattainable score
is in the same residue class as
.
The largest member of this residue class less than is
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 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
See Also
This article is a stub. Help us out by expanding it.