|
|
| Line 1: |
Line 1: |
| − | The '''Chicken McNugget Theorem''' (or '''Postage Stamp Problem''' or '''Frobenius Coin 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>.
| + | <math>\xyz</math> |
| − | | |
| − | A consequence of the theorem is that there are exactly <math>\frac{(m - 1)(n - 1)}{2}</math> positive integers which cannot be expressed in the form <math>am + bn</math>. The proof is based on the fact that in each pair of the form <math>(k, (m - 1)(n - 1) - k+1)</math>, exactly one element is expressible.
| |
| − | | |
| − | == Origins ==
| |
| − | There are many stories surrounding the origin of the Chicken McNugget theorem. However, the most popular by far remains that of the Chicken McNugget. Originally, McDonald's sold its nuggets in packs of 9 and 20. Math enthusiasts were curious to find the largest number of nuggets that could not have been bought with these packs, thus creating the Chicken McNugget Theorem (the answer worked out to be 151 nuggets). The Chicken McNugget Theorem has also been called the Frobenius Coin Problem or the Frobenius Problem, after German mathematician Ferdinand Frobenius inquired about the largest amount of currency that could not have been made with certain types of coins.
| |
| − | | |
| − | ==Proof Without Words==
| |
| − | <math>\begin{array}{ccccccc}
| |
| − | 0\mod{m}&1\mod{m}&2\mod{m}&...&...&...&(m-1)\mod{m}\\
| |
| − | \hline
| |
| − | \cancel{0n}&1&2&&...&&m-1\\
| |
| − | \cancel{0n+m}&...&&\vdots&&...&\\
| |
| − | \cancel{0n+2m}&...&&\cancel{1n}&&...&\\
| |
| − | \cancel{0n+3m}&&&\cancel{1n+m}&&\vdots&\\
| |
| − | \cancel{0n+4m}&&&\cancel{1n+2m}&&\cancel{2n}&\\
| |
| − | \cancel{0n+5m}&&&\cancel{1n+3m}&&\cancel{2n+m}&\\
| |
| − | \vdots&&&\vdots&&\vdots&\\
| |
| − | \cancel{\qquad}&\cancel{\qquad}&\cancel{ \qquad}&\cancel{ \qquad}&\mathbf{(m-1)n-m}&\cancel{\qquad }&\cancel{\qquad }\\
| |
| − | \cancel{\qquad}&\cancel{\qquad}&\cancel{ \qquad}&\cancel{ \qquad}&\cancel{(m-1)n}&\cancel{\qquad }&\cancel{\qquad }
| |
| − | \end{array}</math> | |
Revision as of 21:11, 30 November 2020
$\xyz$ (Error compiling LaTeX. Unknown error_msg)
