美国职业橄榄球赛季正在进行,每周都有大量关于赛程和强强对话的搜索。看多了比分会发现一个规律:17、20、23、24、27 经常出现,而 1 分从未出现。这不是巧合。每个比分背后都藏着一个经典的数论问题:哪些整数可以写成若干固定数值之和?
每种得分方式值多少分
按照职业橄榄球规则,达阵(touchdown)得 6 分。之后进攻方尝试附加分:踢球附加分得 1 分,两分转换得 2 分。射门(field goal)得 3 分,安全分(safety)得 2 分。把达阵和附加分合在一起,一次完整的得分为 2、3、6、7 或 8 分。
1 分从不单独出现,它只能跟在达阵之后。因此对最终比分来说,关键的集合是 。
核心概念:非负整数系数的线性组合
比分 可能出现,当且仅当存在非负整数 (每种得分出现的次数),使得:
注意 6、7、8 并没有带来新东西:6 = 3 + 3,7 = 2 + 2 + 3,8 = 2 + 3 + 3。所以只需研究 2 和 3。从 2 开始的偶数都是若干个 2 之和;从 3 开始的奇数都是一个 3 加若干个 2。结论:所有 的整数都能达到,1 是唯一的空缺(0 分表示没有得分)。
硬币问题(又称麦乐鸡问题)
现在设想一个虚构联赛,只有 3 分和 7 分两种得分方式。这就是硬币问题的体育版:只有面值 3 元和 7 元的硬币,哪些金额可以不找零地正好付清?它也常被称为麦乐鸡问题,因为鸡块按固定数量装盒出售。
两个事实决定一切。第一,若 ,只有 的倍数可以达到,有无穷多个数被漏掉。第二,若 ,存在一个最大的不可达数,称为 Frobenius 数:
对于 3 和 7,。不可达比分的个数也有公式:,结果为 6。列出来正是 1、2、4、5、8、11。
例题:凑出 24 分有几种方式?
在只有 3 分和 7 分的虚构联赛中,一支球队最终得了 24 分。有哪些得分组合?我们要求 的非负整数解。
- b 乘的是较大的数,取值很少:7b 不能超过 24,所以 b 只能是 0、1、2 或 3。
- 用整除筛选:24 - 7b 必须是 3 的倍数。7 除以 3 余 1,24 除以 3 余 0,所以 b 必须是 3 的倍数。
- 剩下 b = 0 和 b = 3。
- 当 b = 0 时:3a = 24,所以 a = 8(八次 3 分)。
- 当 b = 3 时:3a = 24 - 21 = 3,所以 a = 1(一次 3 分和三次 7 分)。
- 验证:3 × 8 + 7 × 0 = 24,3 × 1 + 7 × 3 = 3 + 21 = 24。两种组合都正确,且没有其他组合。
为什么从 12 开始都可以
论证很简洁:12 = 3 × 4,13 = 3 × 2 + 7,14 = 7 × 2,这是三个连续的可达数。每加一次 3 分,就得到模 3 余数相同的下一个数,所以 15、16、17 以及之后的所有数都可达。之所以三个连续就够,是因为最小的得分是 3,这与整除证明中的归纳思想相同。
常见错误
- 以为最大公约数为 1 就什么都能凑出。 它只保证超过某个值之后都可达,并不是每个数都可达。用 3 和 7 时,11 仍然不可能。
- 允许负系数。 方程 有整数解(,),但没有人能得到“负两个射门”。硬币问题要求系数非负。
- 没有检查 b 的所有取值。 找到第一个解就停下会漏掉组合,24 分的例子就说明了这一点。
- 把附加分当作独立得分。 它依附于达阵;单独计算会错误地得出 1 分可能出现的结论。
常见问题
橄榄球比赛能以 1 分结束吗?
不能。附加分只在达阵之后出现,而能单独得分的方式都至少 2 分。由于 2 和 3 能凑出所有从 2 开始的整数,唯一不可能的最终比分是 1。
什么是 Frobenius 数?
它是无法用给定数值的非负整数组合表示的最大整数。对于最大公约数为 1 的两个数 a 和 b,它等于 ab - a - b。对 3 和 7 来说是 11。
如果这些数有大于 1 的公约数呢?
那么只有最大公约数的倍数能达到。例如只有 4 分和 6 分时,任何奇数比分都不可能,也不存在最大的不可达数。
三个或更多数值有公式吗?
三个或更多数值没有通用的封闭公式,通常用算法或按余数分析,就像我们处理 2 和 3 那样。