随笔 - Chicken McNugget 定理 (麦乐鸡定理)

两个整数的正线性组合所不能表示的最大数是多少?

定理 - 1-1 (Chicken McNugget 定理) 对任意两个 互素 的正整数 \(a,b\), 令

\[ A=\mathbb{Z}\setminus\{ax+by:x,y\in\mathbb{N}\} \]

\[ \max A=ab-a-b \]

直观理解

\(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\)

推论

推论 - 1-1 对任意整数 \(k\), \(k\in A\)\(ab-a-b-k\in A\) 恰有一个成立

推广

定理 - 1-2 对任意两个正整数 \(a,b\), 令

\[ A=\mathbb{Z}\setminus\{ax+by:x,y\in\mathbb{N}\} \]

\[ \max A=\operatorname{lcm}\{a,b\}-a-b \]

证明

注意到

\[ ax+by=\gcd\{a,b\}\left(x\frac{a}{\gcd\{a,b\}}+y\frac{b}{\gcd\{a,b\}}\right) \]

对括号内的部分应用 定理 - 1-1, 则

\[ \begin{aligned} \max A&=\gcd\{a,b\}\left(\frac{ab}{\gcd^2\{a,b\}}-\frac{a}{\gcd\{a,b\}}-\frac{b}{\gcd\{a,b\}}\right)\\ &=\operatorname{lcm}\{a,b\}-a-b \end{aligned} \]

参考资料