Frobenius问题（硬币问题）

Posted on In Word count in article: 1.6k Reading time ≈ 6 mins.

两个生活小问题

在了解Frobenius问题之前, 我们先来看两个生活中的小问题.

首先, 为什么高铁的座位设置大多是 “2+3” 的组合？即过道一侧是两个座位组合在一起、另一侧是三个座位组合在一起呢？设想一下, 当你和家人或是朋友出行时, 不管你们人数是多少, 只要不少于两人, 总有一种座位组合方式让每一个人和认识的人坐在一起, 而不会出现落单的情况. 当出行人数是偶数时, 只需都安排两人坐即可；当出行人数是奇数时, 只需安排三个人坐三人座, 剩下的人（如果有的话）一定是偶数, 再安排两人座若干即可.

我们再看第二个问题：给定几种面值的硬币, 不能用这些硬币支付的最大金额是多少？

假设你现在去便利店买东西, 现在有若干面值的硬币：￥2, ￥3, ￥5, ￥7, 你只可以选其中两种放进你的钱包（数量不限）. 你不知道你要买的东西具体的价格, 并且便利店不设找零, 所以你希望用这两种面值的硬币去组合出尽可能多的数值, 你会怎么选？

假如现在你选了￥3和￥5, 那么从不小于￥5的商品开始逐一验证, 我们发现如果商品的价格是￥7就无法组合出来, 不过价格超过￥7 时似乎都可以表示出来；接着我们选￥3和￥7继续做试验, 我们发现￥8, ￥11 都是无法用￥3 和￥7 组合出来的, 那么大于￥11的情形是否都满足可以用这两种面额的硬币进行组合呢？逐一验证的方法显然无法严格证明.

两个数学问题

我们先不急着回答刚才的问题, 而是先看两道数学问题.

问题 1

设正整数 互素. 证明：不定方程 没有非负整数解.

问题 2
设正整数 互素, 且正整数 满足 . 证明：不定方程 有非负整数解.

事实上, 上述两个问题说的是同一件事, 也即是：对于不定方程 , 只要 , 方程 就有非负整数解.

问题1的证明

采用反证法. 若存在非负整数对 满足该不定方程, 则 ， 此时应有 , 因为 , 故 , 由于 与 均为正整数, 得 .

同理可证：, 进而 . 但此时左边满足 而右边为 , 矛盾.

因此, 原方程没有非负整数解.

问题2的证明

这里我们要用到二元一次不定方程通解的概念. 现设方程的通解为
其中 为方程的特解.

通过调节 的值（对 增减 ）, 可找到一个解 使得 . 此时
故, 即 . 这表明 是方程的非负整数解, 命题得证.

Frobenius问题（硬币问题）

Frobenius问题（又称硬币问题）的核心是研究给定一组互素的正整数 时, 无法表示为这些数的非负整数线性组合的最大整数. 这个最大不可表数被称为 Frobenius数, 记作 . 例如, 对于互素的 和 , Sylvester 在 1884 年证明了 , 这正是前文问题 1 和 2 中提到的临界值 .

该问题由德国数学家 Ferdinand Georg Frobenius 在 19 世纪末提出, 但更早的研究可追溯至英国数学家 James Joseph Sylvester. Sylvester 在讨论“鸡块问题”时, 已揭示了二元情形的解：若鸡块包装为 7 块和 11 块, 则最大无法购买的块数为 59. 这一具体案例被广泛用于数学教学中, 成为经典例题.

虽然二元情形已有明确公式, 但当变量数 时, Frobenius数尚无通用解法. 数学家 Issai Schur 曾称其为“数论中看似简单却极难的问题”. 目前已知： 1. 三元及以上无通解：即使对 , 仅在某些特殊条件下存在部分公式（如等差数列或特定互素组合）. 2. 计算复杂度：确定 Frobenius数属于 NP 难问题, 当 较大时需依赖算法或近似计算. 3. 实际应用：该问题在资源调度、密码学、物流规划中均有应用. 例如, 优化自动售货机的硬币找零系统.

最后是相关领域的一些扩展与应用：

  1. 代数拓扑的联系
    广义弱双 Frobenius 代数上的等变循环上同调研究, 揭示了该问题在代数结构与拓扑不变性中的深层联系. 例如, 等变循环上同调的不变量可能与 Frobenius数的计算相关.

  2. 组合优化与算法
    目前主流的算法包括：
    • 穷举法：通过模运算缩小搜索范围（如对二元情形取模 或 ）.
    • 差分法：利用动态规划标记可表数.
    • 几何方法：将问题转化为格点覆盖问题, 分析超立方体的覆盖间隙.

  3. 未解之谜
    对 的情形, 数学家仅能通过条件约束（如 且互素）或特定结构（如等差数列）推导部分结果. 例如, 若 成等差数列且互素, 则 （需验证条件）.