|
|
给定面额为 $a$ 和 $b$ 的硬币（正整数且互质），能否给出一个公式 $g(a,b)$ 来表示无法用这些硬币兑换出的最大金额？这一问题及其推广到任意面额 $a_1,a_2,\dots,a_n$ 的情况，被称为 Frobenius 硬币兑换问题。
aimath.org/~circle/theteacherscircle.org/reso … s/beck.frobenius.pdf
记
$$
r_k=\#\{(m,n)\in\mathbb Z_{\ge0}^2: ma+nb=k\},
$$
即能用非负整数倍的 $a$ 和 $b$ 表示 $k$ 的方法数。
- 对任意 $k\ge0$，都有
$$
r_{k+ab}=r_k+1.
$$
证明：将等式 $ma+nb=k+ab$ 的所有解分为两类——一类是 $m\ge b$，通过取 $(m',n')=(m-b,n+a)$ 与 $ma+nb=k$ 的解一一对应，得到 $r_k$ 个解；另一类是 $0\le m<b$，利用 $\gcd(a,b)=1$ 可知此时恰有唯一解，合计正好多出 1。 - $$
\sum_{k\ge0}r_k\,x^k
=\frac1{(1-x^a)\,(1-x^b)}.
$$证明：由定义直接写成双重求和
$$
\sum_{m,n\ge0}x^{ma+nb}
=\Bigl(\sum_{m\ge0}(x^a)^m\Bigr)\Bigl(\sum_{n\ge0}(x^b)^n\Bigr)
=\frac1{1-x^a}\cdot\frac1{1-x^b}.
$$ - 令 $s_k=\min(1,r_k)$ 则
$$
\sum_{k\ge0}s_k\,x^k
=\frac{1 - x^{ab}}{(1-x^a)\,(1-x^b)}.
$$
证明：记 $G(x)=\sum r_kx^k=1/[(1-x^a)(1-x^b)]$，则
$$
(1-x^{ab})G(x)
=\sum\bigl(r_k - r_{k-ab}\bigr)x^k.
$$
根据1，当 $k\ge ab$ 时 $r_k-r_{k-ab}=1$，当 $k<ab$ 时由于互质性，任何可表示的 $k$ 只有唯一拆分，故 $r_k=s_k$。综上得所求公式。
|
|
