Chicken McNugget Theorem
From AoPSWiki
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 
.
Contents |
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
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.
