Difference between revisions of "Chicken McNugget Theorem"
m (Fix typo.) |
(→Intermediate) |
||
(98 intermediate revisions by 45 users not shown) | |||
Line 1: | Line 1: | ||
− | 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>. | + | 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>. |
− | 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, | + | 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, mn-m-n-k)</math>, exactly one element is expressible. |
== Origins == | == 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== | + | ==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> | ||
+ | |||
+ | |||
+ | Example using m=<math>\color{magenta}11</math> and n=<math>\color{blue}4</math> | ||
+ | |||
+ | <math> | ||
+ | \begin{array}{ccccccccccc} | ||
+ | 0 & 1 & 2 & 3 & \color{blue}\cancel{4}& 5 & 6 & 7 & \color{blue}\cancel{8} & 9 & 10 \\ | ||
+ | \color{magenta}\cancel{11} & \color{blue}\cancel{12} & 13 & 14 & \cancel{15} & \color{blue}\cancel{16} & 17 & 18 & \cancel{19} & \color{blue}\cancel{20} & 21 \\ | ||
+ | \cancel{22} & \cancel{23} & \color{blue}\cancel{24} & 25 & \cancel{26} & \cancel{27} & \color{blue}\cancel{28} & \color{red}\bold 29 & \cancel{30} & \cancel{31} & \color{blue}\cancel{32} \\ | ||
+ | \cancel{33} & \cancel{34} & \cancel{35} & \color{blue}\cancel{36} & \cancel{37} & \cancel{38} & \cancel{39} & \color{blue}\cancel{40} & \cancel{41} & \cancel{42} & \cancel{43} \\ | ||
+ | \cancel{44} & \cancel{ 45 } & \cancel{ 46 } & \cancel{ 47 } & \cancel{ 48 } & \cancel{ 49 } & \cancel{ 50 } & \cancel{ 51 } & \cancel{ 52 } & \cancel{ 53 } & \cancel{ 54 }\\ | ||
+ | \cancel{55} & \cancel{ 56 } & \cancel{ 57 } & \cancel{ 58 } & \cancel{ 59 } & \cancel{ 60 } & \cancel{ 61 } & \cancel{ 62 } & \cancel{ 63 } & \cancel{ 64 } & \cancel{ 65 } \\ | ||
+ | \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\\ | ||
+ | \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} \\ | ||
+ | \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} & \cancel{\qquad} \\ | ||
+ | |||
+ | \end{array} | ||
+ | </math> | ||
+ | |||
+ | ==Proof 1== | ||
<b>Definition</b>. An integer <math>N \in \mathbb{Z}</math> will be called <i>purchasable</i> if there exist nonnegative integers <math>a,b</math> such that <math>am+bn = N</math>. | <b>Definition</b>. An integer <math>N \in \mathbb{Z}</math> will be called <i>purchasable</i> if there exist nonnegative integers <math>a,b</math> such that <math>am+bn = N</math>. | ||
− | We would like to prove that <math>mn-m-n</math> is the largest non-purchasable integer. We are required to show that (1) <math>mn-m-n</math> is non-purchasable | + | We would like to prove that <math>\text{ }mn-m-n\text{ }</math> is the largest non-purchasable integer. We are required to show that: |
+ | |||
+ | (1) <math>\text{ }mn-m-n\text{ }</math> is non-purchasable | ||
+ | |||
+ | (2) Every <math>N > mn-m-n</math> is purchasable | ||
+ | |||
Note that all purchasable integers are nonnegative, thus the set of non-purchasable integers is nonempty. | Note that all purchasable integers are nonnegative, thus the set of non-purchasable integers is nonempty. | ||
<b>Lemma</b>. Let <math>A_{N} \subset \mathbb{Z} \times \mathbb{Z}</math> be the set of solutions <math>(x,y)</math> to <math>xm+yn = N</math>. Then <math>A_{N} = \{(x+kn,y-km) \;:\; k \in \mathbb{Z}\}</math> for any <math>(x,y) \in A_{N}</math>. | <b>Lemma</b>. Let <math>A_{N} \subset \mathbb{Z} \times \mathbb{Z}</math> be the set of solutions <math>(x,y)</math> to <math>xm+yn = N</math>. Then <math>A_{N} = \{(x+kn,y-km) \;:\; k \in \mathbb{Z}\}</math> for any <math>(x,y) \in A_{N}</math>. | ||
− | <i>Proof</i>: By Bezout, there exist integers <math>x',y'</math> such that <math>x'm+y'n = 1</math>. Then <math>(Nx')m+(Ny')n = N</math>. Hence <math>A_{N}</math> is nonempty. It is easy to check that <math>(Nx'+kn,Ny'-km) \in A_{N}</math> for all <math>k \in \mathbb{Z}</math>. We now prove that there are no others. Suppose <math>(x_{1},y_{1})</math> and <math>(x_{2},y_{2})</math> are solutions to <math>xm+yn=N</math>. Then <math>x_{1}m+y_{1}n = x_{2}m+y_{2}n</math> implies <math>m(x_{1}-x_{2}) = n(y_{2}-y_{1})</math>. Since <math>m</math> and <math>n</math> are coprime and <math>m</math> divides <math>n(y_{2}-y_{1})</math>, <math>m</math> divides <math>y_{2}-y_{1}</math> and <math>y_{2} \equiv y_{1} \pmod{m}</math>. Similarly <math>x_{2} \equiv x_{1} \pmod{n}</math>. Let <math>k_{1},k_{2}</math> be integers such that <math>x_{2}-x_{1} = k_{1}n</math> and <math>y_{2}-y_{1} = k_{2}m</math>. Then <math>( | + | <i>Proof</i>: By [[Bezout's Lemma]], there exist integers <math>x',y'</math> such that <math>x'm+y'n = 1</math>. Then <math>(Nx')m+(Ny')n = N</math>. Hence <math>A_{N}</math> is nonempty. It is easy to check that <math>(Nx'+kn,Ny'-km) \in A_{N}</math> for all <math>k \in \mathbb{Z}</math>. We now prove that there are no others. Suppose <math>(x_{1},y_{1})</math> and <math>(x_{2},y_{2})</math> are solutions to <math>xm+yn=N</math>. Then <math>x_{1}m+y_{1}n = x_{2}m+y_{2}n</math> implies <math>m(x_{1}-x_{2}) = n(y_{2}-y_{1})</math>. Since <math>m</math> and <math>n</math> are coprime and <math>m</math> divides <math>n(y_{2}-y_{1})</math>, <math>m</math> divides <math>y_{2}-y_{1}</math> and <math>y_{2} \equiv y_{1} \pmod{m}</math>. Similarly <math>x_{2} \equiv x_{1} \pmod{n}</math>. Let <math>k_{1},k_{2}</math> be integers such that <math>x_{2}-x_{1} = k_{1}n</math> and <math>y_{2}-y_{1} = k_{2}m</math>. Then <math>m(-k_{1}n) = n(k_{2}m)</math> implies <math>k_{1} = -k_{2}.</math> We have the desired result. <math>\square</math> |
<b>Lemma</b>. For any integer <math>N</math>, there exists unique <math>(a_{N},b_{N}) \in \mathbb{Z} \times \{0,1,\ldots,m-1\}</math> such that <math>a_{N}m + b_{N}n = N</math>. | <b>Lemma</b>. For any integer <math>N</math>, there exists unique <math>(a_{N},b_{N}) \in \mathbb{Z} \times \{0,1,\ldots,m-1\}</math> such that <math>a_{N}m + b_{N}n = N</math>. | ||
− | <i>Proof</i>: By the division algorithm, there exists <math>k</math> such that <math>0 \le y-km \le m-1</math>. <math>\square</math> | + | <i>Proof</i>: By the division algorithm, there exists one and only one <math>k</math> such that <math>0 \le y-km \le m-1</math>. <math>\square</math> |
<b>Lemma</b>. <math>N</math> is purchasable if and only if <math>a_{N} \ge 0</math>. | <b>Lemma</b>. <math>N</math> is purchasable if and only if <math>a_{N} \ge 0</math>. | ||
− | <i>Proof</i>: If <math>a_{N} \ge 0</math>, then we may simply pick <math>(a,b) = (a_{N},b_{N})</math> so <math>N</math> is purchasable. If <math>a_{N} < 0</math>, then <math>a_{N}+kn < 0</math> if <math>k \ | + | <i>Proof</i>: If <math>a_{N} \ge 0</math>, then we may simply pick <math>(a,b) = (a_{N},b_{N})</math> so <math>N</math> is purchasable. If <math>a_{N} < 0</math>, then <math>a_{N}+kn < 0</math> if <math>k \le 0</math> and <math>b_{N}-km < 0</math> if <math>k > 0</math>, hence at least one coordinate of <math>(a_{N}+kn,b_{N}-km)</math> is negative for all <math>k \in \mathbb{Z}</math>. Thus <math>N</math> is not purchasable. <math>\square</math> |
Thus the set of non-purchasable integers is <math>\{xm+yn \;:\; x<0,0 \le y \le m-1\}</math>. We would like to find the maximum of this set. | Thus the set of non-purchasable integers is <math>\{xm+yn \;:\; x<0,0 \le y \le m-1\}</math>. We would like to find the maximum of this set. | ||
Since both <math>m,n</math> are positive, the maximum is achieved when <math>x = -1</math> and <math>y = m-1</math> so that <math>xm+yn = (-1)m+(m-1)n = mn-m-n</math>. | Since both <math>m,n</math> are positive, the maximum is achieved when <math>x = -1</math> and <math>y = m-1</math> so that <math>xm+yn = (-1)m+(m-1)n = mn-m-n</math>. | ||
− | ==Problems= | + | ==Proof 2== |
+ | We start with this statement taken from [[Fermat%27s_Little_Theorem#Proof_2_.28Inverses.29|Proof 2 of Fermat's Little Theorem]]: | ||
+ | |||
+ | "Let <math>S = \{1,2,3,\cdots, p-1\}</math>. Then, we claim that the set <math>a \cdot S</math>, consisting of the product of the elements of <math>S</math> with <math>a</math>, taken modulo <math>p</math>, is simply a permutation of <math>S</math>. In other words, | ||
+ | |||
+ | <center><cmath>S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.</cmath></center><br> | ||
+ | |||
+ | Clearly none of the <math>ia</math> for <math>1 \le i \le p-1</math> are divisible by <math>p</math>, so it suffices to show that all of the elements in <math>a \cdot S</math> are distinct. Suppose that <math>ai \equiv aj \pmod{p}</math> for <math>i \neq j</math>. Since <math>\text{gcd}\, (a,p) = 1</math>, by the cancellation rule, that reduces to <math>i \equiv j \pmod{p}</math>, which is a contradiction." | ||
+ | |||
+ | Because <math>m</math> and <math>n</math> are coprime, we know that multiplying the residues of <math>m</math> by <math>n</math> simply permutes these residues. Each of these permuted residues is purchasable (using the definition from Proof 1), because, in the form <math>am+bn</math>, <math>a</math> is <math>0</math> and <math>b</math> is the original residue. We now prove the following lemma. | ||
+ | |||
+ | <b>Lemma</b>: For any nonnegative integer <math>c < m</math>, <math>cn</math> is the least purchasable number <math>\equiv cn \bmod m</math>. | ||
+ | |||
+ | <i>Proof</i>: Any number that is less than <math>cn</math> and congruent to it <math>\bmod m</math> can be represented in the form <math>cn-dm</math>, where <math>d</math> is a positive integer. If this is purchasable, we can say <math>cn-dm=am+bn</math> for some nonnegative integers <math>a, b</math>. This can be rearranged into <math>(a+d)m=(c-b)n</math>, which implies that <math>(a+d)</math> is a multiple of <math>n</math> (since <math>\gcd(m, n)=1</math>). We can say that <math>(a+d)=gn</math> for some positive integer <math>g</math>, and substitute to get <math>gmn=(c-b)n</math>. Because <math>c < m</math>, <math>(c-b)n < mn</math>, and <math>gmn < mn</math>. We divide by <math>mn</math> to get <math>g<1</math>. However, we defined <math>g</math> to be a positive integer, and all positive integers are greater than or equal to <math>1</math>. Therefore, we have a contradiction, and <math>cn</math> is the least purchasable number congruent to <math>cn \bmod m</math>. <math>\square</math> | ||
+ | |||
+ | This means that because <math>cn</math> is purchasable, every number that is greater than <math>cn</math> and congruent to it <math>\bmod m</math> is also purchasable (because these numbers are in the form <math>am+bn</math> where <math>b=c</math>). Another result of this Lemma is that <math>cn-m</math> is the greatest number <math>\equiv cn \bmod m</math> that is not purchasable. <math>c \leq m-1</math>, so <math>cn-m \leq (m-1)n-m=mn-m-n</math>, which shows that <math>mn-m-n</math> is the greatest number in the form <math>cn-m</math>. Any number greater than this and congruent to some <math>cn \bmod m</math> is purchasable, because that number is greater than <math>cn</math>. All numbers are congruent to some <math>cn</math>, and thus all numbers greater than <math>mn-m-n</math> are purchasable. | ||
+ | |||
+ | Putting it all together, we can say that for any coprime <math>m</math> and <math>n</math>, <math>mn-m-n</math> is the greatest number not representable in the form <math>am + bn</math> for nonnegative integers <math>a, b</math>. <math>\square</math> | ||
+ | |||
+ | ==Corollary== | ||
+ | This corollary is based off of Proof 2, so it is necessary to read that proof before this corollary. We prove the following lemma. | ||
+ | |||
+ | <b>Lemma:</b> For any integer <math>k</math>, exactly one of the integers <math>k</math>, <math>mn-m-n-k</math> is not purchasable. | ||
+ | |||
+ | <i>Proof</i>: Because every number is congruent to some residue of <math>m</math> permuted by <math>n</math>, we can set <math>k \equiv cn \bmod m</math> for some <math>c</math>. We can break this into two cases. | ||
+ | |||
+ | <i>Case 1</i>: <math>k \leq cn-m</math>. This implies that <math>k</math> is not purchasable, and that <math>mn-m-n-k \geq mn-m-n-(cn-m) = n(m-1-c)</math>. <math>n(m-1-c)</math> is a permuted residue, and a result of the lemma in Proof 2 was that a permuted residue is the least number congruent to itself <math>\bmod m</math> that is purchasable. Therefore, <math>mn-m-n-k \equiv n(m-1-c) \bmod m</math> and <math>mn-m-n-k \geq n(m-1-c)</math>, so <math>mn-m-n-k</math> is purchasable. | ||
+ | |||
+ | <i>Case 2</i>: <math>k > cn-m</math>. This implies that <math>k</math> is purchasable, and that <math>mn-m-n-k < mn-m-n-(cn-m) = n(m-1-c)</math>. Again, because <math>n(m-1-c)</math> is the least number congruent to itself <math>\bmod m</math> that is purchasable, and because <math>mn-m-n-k \equiv n(m-1-c) \bmod m</math> and <math>mn-m-n-k < n(m-1-c)</math>, <math>mn-m-n-k</math> is not purchasable. | ||
+ | |||
+ | We now limit the values of <math>k</math> to all integers <math>0 \leq k \leq \frac{mn-m-n}{2}</math>, which limits the values of <math>mn-m-n-k</math> to <math>mn-m-n \geq mn-m-n-k \geq \frac{mn-m-n}{2}</math>. Because <math>m</math> and <math>n</math> are coprime, only one of them can be a multiple of <math>2</math>. Therefore, <math>mn-m-n \equiv (0)(1)-0-1 \equiv -1 \equiv 1 \bmod 2</math>, showing that <math>\frac{mn-m-n}{2}</math> is not an integer and that <math>\frac{mn-m-n-1}{2}</math> and <math>\frac{mn-m-n+1}{2}</math> are integers. We can now set limits that are equivalent to the previous on the values of <math>k</math> and <math>mn-m-n-k</math> so that they cover all integers form <math>0</math> to <math>mn-m-n</math> without overlap: <math>0 \leq k \leq \frac{mn-m-n-1}{2}</math> and <math>\frac{mn-m-n+1}{2} \leq mn-m-n-k \leq mn-m-n</math>. There are <math>\frac{mn-m-n-1}{2}+1=\frac{(m-1)(n-1)}{2}</math> values of <math>k</math>, and each is paired with a value of <math>mn-m-n-k</math>, so we can make <math>\frac{(m-1)(n-1)}{2}</math> different ordered pairs of the form <math>(k, mn-m-n-k)</math>. The coordinates of these ordered pairs cover all integers from <math>0</math> to <math>mn-m-n</math> inclusive, and each contains exactly one not-purchasable integer, so that means that there are <math>\frac{(m-1)(n-1)}{2}</math> different not-purchasable integers from <math>0</math> to <math>mn-m-n</math>. All integers greater than <math>mn-m-n</math> are purchasable, so that means there are a total of <math>\frac{(m-1)(n-1)}{2}</math> integers <math>\geq 0</math> that are not purchasable. | ||
+ | |||
+ | In other words, for every pair of coprime integers <math>m, n</math>, there are exactly <math>\frac{(m-1)(n-1)}{2}</math> nonnegative integers that cannot be represented in the form <math>am + bn</math> for nonnegative integers <math>a, b</math>. <math>\square</math> | ||
+ | |||
+ | ==Generalization== | ||
+ | If <math>m</math> and <math>n</math> are not relatively prime, then we can simply rearrange <math>am+bn</math> into the form | ||
+ | <cmath>\gcd(m,n) \left( a\frac{m}{\gcd(m,n)}+b\frac{n}{\gcd(m,n)} \right)</cmath> | ||
+ | <math>\frac{m}{\gcd(m,n)}</math> and <math>\frac{n}{\gcd(m,n)}</math> are relatively prime, so we apply Chicken McNugget to find a bound | ||
+ | <cmath>\frac{mn}{\gcd(m,n)^{2}}-\frac{m}{\gcd(m,n)}-\frac{n}{\gcd(m,n)}</cmath> | ||
+ | We can simply multiply <math>\gcd(m,n)</math> back into the bound to get | ||
+ | <cmath>\frac{mn}{\gcd(m,n)}-m-n=\textrm{lcm}(m, n)-m-n</cmath> | ||
+ | Therefore, all multiples of <math>\gcd(m, n)</math> greater than <math>\textrm{lcm}(m, n)-m-n</math> are representable in the form <math>am+bn</math> for some positive integers <math>a, b</math>. | ||
+ | |||
+ | =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? | + | *Marcy buys paint jars in containers of <math>2</math> and <math>7</math>. What's the largest number of paint jars that Marcy can't obtain? |
+ | |||
+ | Answer: <math>5</math> containers | ||
+ | |||
+ | *Bay Area Rapid food sells chicken nuggets. You can buy packages of <math>11</math> or <math>7</math>. What is the largest integer <math>n</math> such that there is no way to buy exactly <math>n</math> nuggets? Can you Generalize ? (Source: The Art and Craft of Problem Solving) | ||
+ | |||
+ | Answer: <math>n=59</math> | ||
+ | |||
+ | *If a game of American Football has only scores of field goals (<math>3</math> points) and touchdowns with the extra point (<math>7</math> points), then what is the greatest score that cannot be the score of a team in this football game (ignoring time constraints)? | ||
+ | |||
+ | Answer: <math>11</math> points | ||
+ | |||
+ | *The town of Hamlet has <math>3</math> people for each horse, <math>4</math> sheep for each cow, and <math>3</math> ducks for each person. Which of the following could not possibly be the total number of people, horses, sheep, cows, and ducks in Hamlet? | ||
+ | |||
+ | <math>\textbf{(A) }41\qquad\textbf{(B) }47\qquad\textbf{(C) }59\qquad\textbf{(D) }61\qquad\textbf{(E) }66</math> (Source: [[2015 AMC 10B Problems/Problem 15|AMC 10B 2015 Problem 15]]) | ||
+ | |||
+ | Answer: <math>47\qquad\textbf{(B) }</math> | ||
===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 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]] | + | *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? (Source: [[1994 AIME Problems/Problem 11|AIME]]) |
+ | |||
+ | *Find the sum of all positive integers <math>n</math> such that, given an unlimited supply of stamps of denominations <math>5,n,</math> and <math>n+1</math> cents, <math>91</math> cents is the greatest postage that cannot be formed. (Source: [[2019 AIME II Problems/Problem 14|AIME II 2019 Problem 14]]) | ||
===Olympiad=== | ===Olympiad=== | ||
− | On the real number line, paint red all points that correspond to integers of the form <math>81x+100y</math>, where <math>x</math> and <math>y</math> are positive integers. Paint the remaining integer | + | *On the real number line, paint red all points that correspond to integers of the form <math>81x+100y</math>, where <math>x</math> and <math>y</math> are positive integers. Paint the remaining integer points blue. Find a point <math>P</math> on the line such that, for every integer point <math>T</math>, the reflection of <math>T</math> with respect to <math>P</math> is an integer point of a different colour than <math>T</math>. (Source: India TST) |
==See Also== | ==See Also== | ||
Line 41: | Line 141: | ||
*[[Prime]] | *[[Prime]] | ||
− | |||
[[Category:Theorems]] | [[Category:Theorems]] | ||
[[Category:Number theory]] | [[Category:Number theory]] |
Revision as of 19:22, 24 February 2024
The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers , the greatest integer that cannot be written in the form
for nonnegative integers
is
.
A consequence of the theorem is that there are exactly positive integers which cannot be expressed in the form
. The proof is based on the fact that in each pair of the form
, exactly one element is expressible.
Contents
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
Example using m= and n=
Proof 1
Definition. An integer will be called purchasable if there exist nonnegative integers
such that
.
We would like to prove that is the largest non-purchasable integer. We are required to show that:
(1) is non-purchasable
(2) Every is purchasable
Note that all purchasable integers are nonnegative, thus the set of non-purchasable integers is nonempty.
Lemma. Let be the set of solutions
to
. Then
for any
.
Proof: By Bezout's Lemma, there exist integers such that
. Then
. Hence
is nonempty. It is easy to check that
for all
. We now prove that there are no others. Suppose
and
are solutions to
. Then
implies
. Since
and
are coprime and
divides
,
divides
and
. Similarly
. Let
be integers such that
and
. Then
implies
We have the desired result.
Lemma. For any integer , there exists unique
such that
.
Proof: By the division algorithm, there exists one and only one such that
.
Lemma. is purchasable if and only if
.
Proof: If , then we may simply pick
so
is purchasable. If
, then
if
and
if
, hence at least one coordinate of
is negative for all
. Thus
is not purchasable.
Thus the set of non-purchasable integers is . We would like to find the maximum of this set.
Since both
are positive, the maximum is achieved when
and
so that
.
Proof 2
We start with this statement taken from Proof 2 of Fermat's Little Theorem:
"Let . Then, we claim that the set
, consisting of the product of the elements of
with
, taken modulo
, is simply a permutation of
. In other words,
![\[S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.\]](http://latex.artofproblemsolving.com/9/e/3/9e3fcc9c2595bb1f400d5eeda2f8b487a50c4d5c.png)
Clearly none of the for
are divisible by
, so it suffices to show that all of the elements in
are distinct. Suppose that
for
. Since
, by the cancellation rule, that reduces to
, which is a contradiction."
Because and
are coprime, we know that multiplying the residues of
by
simply permutes these residues. Each of these permuted residues is purchasable (using the definition from Proof 1), because, in the form
,
is
and
is the original residue. We now prove the following lemma.
Lemma: For any nonnegative integer ,
is the least purchasable number
.
Proof: Any number that is less than and congruent to it
can be represented in the form
, where
is a positive integer. If this is purchasable, we can say
for some nonnegative integers
. This can be rearranged into
, which implies that
is a multiple of
(since
). We can say that
for some positive integer
, and substitute to get
. Because
,
, and
. We divide by
to get
. However, we defined
to be a positive integer, and all positive integers are greater than or equal to
. Therefore, we have a contradiction, and
is the least purchasable number congruent to
.
This means that because is purchasable, every number that is greater than
and congruent to it
is also purchasable (because these numbers are in the form
where
). Another result of this Lemma is that
is the greatest number
that is not purchasable.
, so
, which shows that
is the greatest number in the form
. Any number greater than this and congruent to some
is purchasable, because that number is greater than
. All numbers are congruent to some
, and thus all numbers greater than
are purchasable.
Putting it all together, we can say that for any coprime and
,
is the greatest number not representable in the form
for nonnegative integers
.
Corollary
This corollary is based off of Proof 2, so it is necessary to read that proof before this corollary. We prove the following lemma.
Lemma: For any integer , exactly one of the integers
,
is not purchasable.
Proof: Because every number is congruent to some residue of permuted by
, we can set
for some
. We can break this into two cases.
Case 1: . This implies that
is not purchasable, and that
.
is a permuted residue, and a result of the lemma in Proof 2 was that a permuted residue is the least number congruent to itself
that is purchasable. Therefore,
and
, so
is purchasable.
Case 2: . This implies that
is purchasable, and that
. Again, because
is the least number congruent to itself
that is purchasable, and because
and
,
is not purchasable.
We now limit the values of to all integers
, which limits the values of
to
. Because
and
are coprime, only one of them can be a multiple of
. Therefore,
, showing that
is not an integer and that
and
are integers. We can now set limits that are equivalent to the previous on the values of
and
so that they cover all integers form
to
without overlap:
and
. There are
values of
, and each is paired with a value of
, so we can make
different ordered pairs of the form
. The coordinates of these ordered pairs cover all integers from
to
inclusive, and each contains exactly one not-purchasable integer, so that means that there are
different not-purchasable integers from
to
. All integers greater than
are purchasable, so that means there are a total of
integers
that are not purchasable.
In other words, for every pair of coprime integers , there are exactly
nonnegative integers that cannot be represented in the form
for nonnegative integers
.
Generalization
If and
are not relatively prime, then we can simply rearrange
into the form
and
are relatively prime, so we apply Chicken McNugget to find a bound
We can simply multiply
back into the bound to get
Therefore, all multiples of
greater than
are representable in the form
for some positive integers
.
Problems
Introductory
- Marcy buys paint jars in containers of
and
. What's the largest number of paint jars that Marcy can't obtain?
Answer: containers
- Bay Area Rapid food sells chicken nuggets. You can buy packages of
or
. What is the largest integer
such that there is no way to buy exactly
nuggets? Can you Generalize ? (Source: The Art and Craft of Problem Solving)
Answer:
- If a game of American Football has only scores of field goals (
points) and touchdowns with the extra point (
points), then what is the greatest score that cannot be the score of a team in this football game (ignoring time constraints)?
Answer: points
- The town of Hamlet has
people for each horse,
sheep for each cow, and
ducks for each person. Which of the following could not possibly be the total number of people, horses, sheep, cows, and ducks in Hamlet?
(Source: AMC 10B 2015 Problem 15)
Answer:
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: AIME)
- Find the sum of all positive integers
such that, given an unlimited supply of stamps of denominations
and
cents,
cents is the greatest postage that cannot be formed. (Source: AIME II 2019 Problem 14)
Olympiad
- On the real number line, paint red all points that correspond to integers of the form
, where
and
are positive integers. Paint the remaining integer points blue. Find a point
on the line such that, for every integer point
, the reflection of
with respect to
is an integer point of a different colour than
. (Source: India TST)