一个关于多种不同面值钞票的支付问题

发布时间：2019-12-18

　　[摘要] 讨论了 n 种面值的钞票的支付问题和 n 维环面上的线性同胚问题。这两个表面上看起来完全无关的问题有一个共同点，就是都涉及互质的 n 个整数，而在解决这两个问题时所使用的方法也有一些相似之处。

　　[关键词] 支付;互质的整数;环面;整数矩阵;线性同胚

　　前些日子，一个在银行工作的朋友向笔者提出了如下的问题：

　　问题 1. 假设某人手上有足够的 5 元与 7 元面值的钞票，请问他无法付款的金额最大值是多少?(譬如，8 元，9 元他就无法支付)。

　　这是一个有趣的数学问题，笔者将其称为“一个关于多种不同面值的钞票的支付问题”。

　　以 N 表示所有的正整数的集合。对任 k∈N，记 Nk={1，2，…，k}。如下的命题给出了问题 1 的答案：

　　命题 2. 记 P={1，2，3，4，6，8，9，11，13，16，18，23}。则

　　(1)对任 m∈P 均不存在非负整数 a 和 b 使得 5a+7b=m。

　　(2)对任 n∈N-P 均存在非负整数 a 和 b 使得 5a+7b=n。

　　证.(A)考虑 m=23∈P。假设 5a+7b=23。若 a=0，则 b=23/7;若 a=1，则 b=18/7;若 a=2，则 b=13/7;若 a=3，则 b=8/7;若 a=4，则 b=3/7;若 a≥5，则 b<0。因此，当 m=23 时命题 2 的结论(1)成立。类似地，对任 m∈P-{23}亦可直接验证命题 2 的结论(1)成立。

　　(B)令 Q={5，7，10，12，14，15，17，19，20，21，22，24，25，26，27}。显然，我们可以直接验证命题 2 的结论(2)对每一个 n∈Q 成立，例如，我们有 27=5×4+7×1，等等。

　　(C)令 S 为所有不小于 27 的整数的集合。我们有：

　　断语 2.1. 若命题 2 的结论(2)对某一个 n=k0∈S 成立，则命题 2 的结论(2)对 n=k0+1 亦成立。

　　断语 2.1 的证明. 由断语 2.1 的条件知存在非负整数 a 和 b 使得 5a+7b=k0。若 b≥2，则 k0+1=5 (a+3)+7(b-2);若 b≤1，则由 k0≥27 可推出 a≥4，进而推出 k0+1=5(a-4)+7(b+3)。因此，无论何种情形，断语 2.1 都能成立。

　　在(B)中我们已经指出命题 2 的结论(2)对 n=k0=27 成立。于是，据断语 2.1 可推出命题 2 的结论(2)对每一个 n∈S 成立，进而推出命题 2 的结论(2)对每一个 n∈S∪Q=N-P 成立。命题 2 证完。

　　下面我们将问题 1 推广，考虑面值分别为 v1，v2，…，vn 元的 n 种钞票。

　　定义 3. 设 m 和v1，v2，…，vn 均为整数，n≥1。若存在非负整数 a1，a2，…，an 使得 a1v1+a2v2+… +anvn=m，则称 m 可表示为v1，v2，…，vn 的非负整数系数的线性组合。

　　记 Q(v1，v2，…，vn )={m∈N：m 可表示为v1，v2，…，vn 的非负整数系数的线性组合}，又记 P(v1， v2，…，vn )=N-Q(v1，v2，…，vn )，则 P(v1，v2，…，vn )是不可表示为v1，v2，…，vn 的非负整数系数的线性组合的所有的正整数的集合。

　　按照定义 3，如果 m∈Q(v1，v2，…，vn )，则可以用面值分别为v1，v2，…，vn 元的钞票支付 m 元;如果 m∈P(v1，v2，…，vn )，则不可以用面值分别为v1，v2，…，vn 元的钞票支付 m 元。

　　首先考虑 n=2 的情形，需要如下的引理：

　　引理 4. 设 v 与 w 是互质的整数，v≥w≥1。则存在非负整数 p，q，r，s 使得 pv-qw=1，rw-sv=1。

　　证. 当 w=1 时引理 4 显然成立。下面假定 w>1。此时，存在正整数 k 和 j 使得 v=kw+j，w>j≥ 1，并且 w 与 j 互质。按照归纳假设，我们可以假定引理 4 对 w 与 j 成立，也就是说，存在非负整数 p'，q'，r'，s' 使得 p'w-q'j=1，r'j-s'w=1。将 j=v-kw 代入这两个等式中，可得 p'w-q'(v-kw)=1，r'(v-kw) -s'w=1，推出：

　　(pv+q'k)w-q'v=1，r'v-(r'k+s')w=1。

　　取 p=r'，q=r'k+s'，r=p'+q'k，s=q'，便可得到引理 4 中的那两个等式。

　　引理 4 的证明，实际上用到了辗转相除的方法。在引理 4 中，如果 v 与 w 是具体给定的数字，则 p，q，r，s 可通过有限个四则运算步骤计算出来。但如果 v 与 w 是用字母表示，则 p，q，r，s 虽然都是 v 与 w 的确定的函数，但它们之间的函数关系却难于用人们常见的公式表示。

　　命题 5. 设 v 与 w 是互质的整数，v≥w≥1，又设 p，q，r，s 如引理 4 中所述，则 Q(v，w)劢[qw+ (s-1)v，∞)∩N，也就是说，每一个不小于 qw+(r-1)v 的整数 m 都可以表示为 v 与 w 的非负整数系数的线性组合。

　　证. 当 m=qw+(s-1)v 时我们显然有 m∈Q(v，w)。下面假定对某一个整数 m≥qw+(s-1)v，已经证明 m∈Q(v，w)，也就是说，存在非负整数 a 和 b 使得 m=av+bw。那么，当 a≥s 时我们有：

　　m+1=av+bw+rw-sv=(a-s)v+(b+r)w

　　当 a≤s-1 时，由 bw=m-av≥qw+(s-1)v-av≥qw 可推出 b≥q，从而可以推出：

　　m=av+bw+pv-qw=(a+p)v+(b-q)w。

　　因此，无论 a≥s 还是 a≤s-1 都有 m+1∈Q(v，w)。于是，据归纳法可以得到 Q(v，w)劢[qw+(s-1)v， ∞)∩N。命题 5 证完。 □

　　由命题 5 可知，若 v 与 w 是互质的整数，则 P(v，w)是一个有限集，并且，沿用命题 5 中的记号，我们有 max(P(v，w))≤qw+(s-1)v-1。

　　在命题 2 中，我们可以明确写出集合 P=P(7，5)中的每一个元素。但在命题 5 中，如果 v 与 w 不是具体给定的数字的话，我们便难于知道集合 P(v，w)的构成，甚至难于指出集合 P(v，w)中所含的元素的准确数目。虽然我们知道 P(v，w)有一个上界 qw+(s-1)v-1，但我们难于给出 P(v，w)的上确界 max(P(v，w))与 v 和 w 之间的函数关系的明确的表达式。

　　定义 6. 以 Z 表示所有的整数的集合。设 v1，v2，…，vn∈Z，n≥2，v1，v2，…，vn 不必是两两不同的，但 v1，v2，…，vn 不能全部为 0。记 gcd(v1，v2，…，vn )=max{k∈N：v1 / k，v2 / k，…，vn / k 均是整数}。

　　称 gcd(v1，v2，…，vn )为 v1，v2，…，vn 的最大公约数。若 v1，v2，…，vn 的最大公约数为 1，则称 v1， v2，…，vn 是互质的。需注意的是，互质的 n 个数不一定是两两互质的，例如，-6，10，15 是互质的 3 个整数，其最大公约数为 1，但-6 与 10，-6 与 15 以及 10 与 15 都不是互质的。

　　下面，当我们说到 v1，v2，…，vn 是互质的 n 个整数时，我们总约定 v1，v2，…，vn 不全为 0。

　　命题 7. 设v1，v2，…，vn 是互质的 n 个非负整数，则 P(v1，v2，…，vn )是一个有限集。

　　证.首先考虑 n=2 的情形。不妨假定 v1≥v2。若 v2=0，则必有 v1=1，此时 P(v1，v2 )是一个空集，命题 7 成立。若 v1≥v2≥1，则据命题 5 知命题 7 成立。下面假定对某一个整数 n0≥3，已经证明当 n=n0-1 时命题 7 成立，要继续考虑 n=n0 的情形。

　　若 v1，v2，…，vn 这 n 个数之中有某两个数相同，则可以将其中一个数去掉。若 v1，v2，…，vn 这 n 个数之中有某一个数为 0，则也可以将这个数去掉。因此我们可以假定 v1>v2>…>vn>0。

　　设 w=gcd(v2，…，vn )，则 v2 / w，…，vn / w 是互质的 n-1 个正整数，并且 v1 与 w 互质。据归纳假设，P(v2 / w，…，vn / w)是一个有限集。于是，记 k=max(P(v2 / w，…，vn / w))+1，则对任一整数 j≥k 均有 j∈Q(v2 / w，…，vn / w)，由此可以得到：

　　断语 7.1. 对任一整数 j≥k 均有 jw∈Q(v2，…，vn )。

　　记 v=v1，则 v>w。因 v 与 w 互质，据引理 4 知存在非负整数 p，q，r，s 使得 pv-qw=1，rw-sv=1。记 β=max{qw+(s-1)v，kvw+kw-w}。我们有

　　断语 7.2. Q(v1，v2，…，vn )劢[β，∞)∩N，换言之，每一个不小于 β 的整数都可以表示为v1，v2， …，vn 的非负整数系数的线性组合。

　　断语 7.2 的证明. 设 m≥β 是一个整数。据命题 5 存在知存在非负整数 a 和 b 使得 m=av+bw。若 b≥k，则据断语 7.1 知 bw 可表示为 v2，…，vn 的非负整数系数的线性组合，因而 m 可表示为 v1， v2，…，vn 的非负整数系数的线性组合。

　　一个关于多种不同面值钞票的支付问题相关期刊推荐：《广西财经学院学报》(双月刊)1988年创刊。本刊主要是传播先进的科学文化知识，弘扬民族科学文化，促进国际科学文化交流，探索高等教育、教学及管理诸方面的规律，活跃教学与科研的学术风气，为教学与科研服务。设有：学报论坛、公共财政研究、税收问题、会计理论与实践、企业管理等栏目。