Difference between revisions of "Chicken McNugget Theorem"
(give a problem to it) |
(→Introductory) |
||
Line 18: | Line 18: | ||
==Problems== | ==Problems== | ||
===Introductory=== | ===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=== | ===Intermediate=== |
Revision as of 20:00, 11 September 2009
The Chicken McNugget Theorem states that for any two relatively prime positive integers , the greatest integer that cannot be written in the form
for nonnegative integers
is
.
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 contribues
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.