Difference between revisions of "Chicken McNugget Theorem"
m |
(give a problem to it) |
||
| Line 15: | Line 15: | ||
The largest member of this residue class less than <math>(m-1)n</math> is <math>(m-1)n - m = mn - m - n</math> and the proof is complete. | The largest member of this residue class less than <math>(m-1)n</math> is <math>(m-1)n - m = mn - m - n</math> and the proof is complete. | ||
| + | |||
| + | ==Problems== | ||
| + | ===Introductory=== | ||
| + | |||
| + | ===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 contribues <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=== | ||
| + | |||
==See Also== | ==See Also== | ||
Revision as of 09:17, 9 August 2008
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
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.
