随笔 - Chicken McNugget 定理 (麦乐鸡定理)
两个整数的正线性组合所不能表示的最大数是多少？
直观理解
| \(0\bmod a\) | \(1\bmod a\) | \(2\bmod a\) | \(\dots\) | \(\dots\) | \(\dots\) | \((a-1)\bmod a\) |
|---|---|---|---|---|---|---|
| \(\xcancel{0b}\) | \(1\) | \(2\) | \(\dots\) | \(\dots\) | \(\dots\) | \(a-1\) |
| \(\xcancel{0b+a}\) | \(\dots\) | |||||
| \(\xcancel{\phantom{0b}}\) | \(\xcancel{1b}\) | \(\dots\) | ||||
| \(\vdots\) | \(\vdots\) | |||||
| \(\xcancel{\phantom{0b}}\) | \(\xcancel{\phantom{1b}}\) | \(\dots\) | \(\xcancel{2b}\) | |||
| \(\vdots\) | \(\vdots\) | \(\vdots\) | ||||
| \(\xcancel{\phantom{0b}}\) | \(\xcancel{\phantom{0b}}\) | \(\xcancel{\phantom{0b}}\) | \(\xcancel{\phantom{0b}}\) | \((a-1)b-a\) | \(\xcancel{\phantom{0b}}\) | \(\xcancel{\phantom{0b}}\) |
| \(\xcancel{\phantom{0b}}\) | \(\xcancel{\phantom{0b}}\) | \(\xcancel{\phantom{0b}}\) | \(\xcancel{\phantom{0b}}\) | \(\xcancel{\phantom{(a-1)b-a}}\) | \(\xcancel{\phantom{0b}}\) | \(\xcancel{\phantom{0b}}\) |
证明
如果 \(n\in A\), 那么要想让 \(n\) 最大，我们首先需要让 \(x=-1\) 或者 \(y=-1\)
假设 \(x=-1\), 此时设 \(y=y'\)
我们有通式
\[ \begin{cases} x=-1+bt\\ y=y'-at \end{cases} \]
因为 \(b>1\), \(x\) 随 \(t\) 严格单调递增，\(y\) 随 \(t\) 严格单调递减
所以要想让 \(n\in A\), 我们需要让 \(y\) 在 \(t=1\) 时为负数
即
\[ y'-a<0\implies y'<a \]
由于 \(y'\) 是整数，所以 \(y'\) 最大只能取 \(a-1\)
此时对应的 \(n\) 即为
\[ a\times(-1)+b(a-1)=ab-a-b \]
如果假设 \(y=-1\), 也可推得相似结论
因为我们在这过程中取的都是最大值，所以 \(ab-a-b\) 即为 \(\max A\)
接下来证明: \(n\notin A~(\forall n>ab-a-b)\)
设 \(ax_0+by_0=n,~x_0\geqslant 0\), 则只需证 \(y_0\geqslant 0\)
取 \(x_0=n\bmod b\), 则 \(x_0\in[0,b-1]\), 有
\[ \begin{aligned} by_0&=n-ax_0\\ &\geqslant n-a(b-1)\\ &>ab-a-b-a(b-1)\\ &=-b \end{aligned} \]
即 \(b(y_0+1)>0\), 从而有 \(y_0\geqslant 0\)