凑不出的最大金额，如今有了最紧的上界

想象一台收银机，只收几种硬币，每种数量不限，而且从不找零。有些金额可以恰好付清，有些则永远不行。数学家把这些硬币面值称为生成元（generators），并提出一个看似简单的问题：无法付清的最大金额是多少？

永远付不出的金额

取整数 a₁ < a₂ < … < aₙ，它们没有全体共有的因数。把这些数相加、每个数想用几次就用几次，得到的总和称为“可表示的”。只有有限多个整数不可表示；其中最大的那个就是弗罗贝尼乌斯数 F。（如果其中某个面值是1，那么任何金额都能付清，此时规定 F = −1。）

举个小例子：用面值3、4和6的硬币，可以付3、4、6、7、8以及之后的每一个金额，但永远付不出1、2或5。所以 F = 5。注意3和6有公因数；关键在于没有哪个因数是三者共有的。

对于两种硬币，有一个精确答案，即西尔维斯特公式：F(a₁, a₂) = a₁a₂ − a₁ − a₂。对于三种或更多硬币，工作就在于给 F 定界：证明它不可能超过某个由硬币面值算出的值。

一个顽固的因子2

保罗·埃尔德什（Paul Erdős）和罗纳德·格雷厄姆（Ronald Graham）证明了，在有三个或更多生成元时：

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

其中 aₙ 是最大的面值，aₙ₋₁ 是第二大的面值，n 是面值的个数，⌊ ⌋ 表示向下取整。与西尔维斯特公式一样，它涉及最大的两种硬币。

他们还估计了最坏情形，即当全部 n 个面值都不超过 t 时 F 可能取到的最大值。他们的几个估计之间大约相差2倍，由此产生了一个猜想，被记录为埃尔德什问题第433号（Erdős Problem #433）。雅克·迪克斯米耶（Jacques Dixmier）解决了这个猜想，还证明了一个对任何面值组都成立的更简单的上界：F ≤ aₙ²/(n − 1)。因子2没有了，但第二大的硬币也随之消失了。

两种最大的硬币都保留

浙江大学计算机科学与技术学院的 Lin Chen、Tingwei Hu、Yuchen Mao 和 Guochuan Zhang 想要两全：既没有因子2，又保留第二大的硬币。他们给出的答案对任意两个或更多面值的组合都成立：

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

其中 ⌈ ⌉ 表示向上取整。与埃尔德什和格雷厄姆的结果相比，因子2消失了，代价是除以 n − 1 而不是 n，并且要向上取整。与迪克斯米耶的结果相比，当第二大的硬币比最大的硬币小很多时，新上界可以小得多。

在3、4、6的例子中，埃尔德什和格雷厄姆的上界给出10，迪克斯米耶的给出18，而新上界给出 4 × 3 − 6 − 1 = 5，恰好等于真实值。这并不奇怪：这组面值属于下文所述的极端情形家族，它们正是为恰好达到上界而构造的；论文没有给出在典型面值组上的比较。

按余数给金额分类

证明沿用了埃尔德什和格雷厄姆的路线。把每个金额按它除以最大硬币 aₙ 所得的余数分类。一旦较小硬币的某个和达到了某个余数，再加上若干个 aₙ，就能达到具有该余数的所有更大金额。任务是证明每个余数都能以较低的代价达到。

关键工具是克内泽尔定理（Kneser’s theorem），它说明一个和集至少必须有多大。埃尔德什和格雷厄姆用它证明，大约 aₙ/n 枚硬币的和能覆盖一半以上的余数，然后把硬币数翻倍来覆盖全部余数。这些和中的每枚硬币面值至多为 aₙ₋₁，所以硬币数翻倍，代价也翻倍：因子2由此而来。

新证明使用 ⌈aₙ/(n − 1)⌉ 枚硬币的和。当这些和漏掉一些余数时，克内泽尔定理表明，漏掉的余数并不是随机散布的：它们构成若干个完整的余数族，彼此以固定间隔排列。漏掉的族越多，较小的硬币就必须越密集地挤进每个已达到的族，因此每个这样的族都含有一些小硬币，而达到漏掉的族所需的少数额外硬币代价很低。总代价从不超过 ⌈aₙ/(n − 1)⌉ × aₙ₋₁。

这第一步给出的上界还缺最后的“− 1”。最后这一个单位来自另一个独立的论证，它基于舍克（Scherk）和肯珀曼（Kemperman）关于只能以唯一方式构成的和的一个定理：它表明临界金额 aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ 本身总能付清。根据致谢部分，作者们先证明了较弱的上界；随后 GPT-6 帮助找到了把上界再降低1的论证，还协助证明了该上界无法再降低，并协助润色英文。作者声明，他们对最终稿件负责。

恰好触及极限的情形

这个上界无法再降低：对每个 n ≥ 3，作者们都构造了无穷多组面值，使 F 恰好等于该上界。任取 q ≥ 2，取面值 q, 2q, …, (n − 1)q，再加上 (n − 2)q + 1。除了一个之外，其余都是 q 的倍数，因此它们能付的金额，单靠 q 也都能付。这组面值的表现就像只有 q 和 (n − 2)q + 1 两种硬币，而西尔维斯特公式给出的 F 恰好与新上界吻合。取 n = 3、q = 3，这个配方得到的正是上文3、4、6的例子。

硬币越少，天花板越低

这个上界也可以从密度的角度来解读。它适用于由最小的 i 个面值加上最大面值构成的任何精简组合，只要这些面值仍然没有公因数。去掉硬币只会让支付更难，所以对精简组合证明的天花板，对完整组合同样成立。决定结果的大致是 aᵢ/i，也就是前 i 个面值填充1到 aᵢ 之间整数的密集程度的倒数：最密集的那一组胜出。作者特别指出，只要剩下的硬币仍然没有全体共有的因数，第二大的硬币就可以直接放到一边。

这篇论文停留在纯理论层面：它没有给出新上界在典型硬币组上究竟小多少的数字，而且该上界的最优性（sharpness）只在三种或更多面值的情形下得到了证明。