美国职业橄榄球赛季正在进行,每周都有大量关于赛程和强强对话的搜索。看多了比分会发现一个规律:17、20、23、24、27 经常出现,而 1 分从未出现。这不是巧合。每个比分背后都藏着一个经典的数论问题:哪些整数可以写成若干固定数值之和?

每种得分方式值多少分

按照职业橄榄球规则,达阵(touchdown)得 6 分。之后进攻方尝试附加分:踢球附加分得 1 分,两分转换得 2 分。射门(field goal)得 3 分,安全分(safety)得 2 分。把达阵和附加分合在一起,一次完整的得分为 2、3、6、7 或 8 分。

1 分从不单独出现,它只能跟在达阵之后。因此对最终比分来说,关键的集合是 {2,3,6,7,8}\{2, 3, 6, 7, 8\}。

核心概念:非负整数系数的线性组合

比分 PP 可能出现,当且仅当存在非负整数 a,b,c,d,ea, b, c, d, e(每种得分出现的次数),使得:

P=2a+3b+6c+7d+8e,a,b,c,d,e∈NP = 2a + 3b + 6c + 7d + 8e,\quad a,b,c,d,e \in \mathbb{N}
比分是各得分方式的非负整数线性组合

注意 6、7、8 并没有带来新东西:6 = 3 + 3,7 = 2 + 2 + 3,8 = 2 + 3 + 3。所以只需研究 2 和 3。从 2 开始的偶数都是若干个 2 之和;从 3 开始的奇数都是一个 3 加若干个 2。结论:所有 P≥2P \geq 2 的整数都能达到,1 是唯一的空缺(0 分表示没有得分)。

0123456789+3+2+2+29 − 0 = 3 + 2 + 2 + 2 = 9
只用 2 和 3:从 0 出发,跳一次 3、再跳三次 2,到达 9。从 3 开始的每个奇数都是一个 3 加若干个 2。

硬币问题(又称麦乐鸡问题)

现在设想一个虚构联赛,只有 3 分和 7 分两种得分方式。这就是硬币问题的体育版:只有面值 3 元和 7 元的硬币,哪些金额可以不找零地正好付清?它也常被称为麦乐鸡问题,因为鸡块按固定数量装盒出售。

两个事实决定一切。第一,若 gcd⁡(a,b)=d>1\gcd(a,b)=d>1,只有 dd 的倍数可以达到,有无穷多个数被漏掉。第二,若 gcd⁡(a,b)=1\gcd(a,b)=1,存在一个最大的不可达数,称为 Frobenius 数:

g(a,b)=ab−a−bg(a,b) = ab - a - b
最大公约数为 1 的两个数的 Frobenius 数

对于 3 和 7,g=21−3−7=11g = 21 - 3 - 7 = 11。不可达比分的个数也有公式:(a−1)(b−1)2\frac{(a-1)(b-1)}{2},结果为 6。列出来正是 1、2、4、5、8、11。

04812162024+3+7+7+724 − 0 = 3 + 7 + 7 + 7 = 24
从 0 出发,跳一次 3、再跳三次 7,正好到 24:这是用 3 分和 7 分凑出 24 的两种方式之一。

例题:凑出 24 分有几种方式?

在只有 3 分和 7 分的虚构联赛中,一支球队最终得了 24 分。有哪些得分组合?我们要求 3a+7b=243a + 7b = 24 的非负整数解。

在非负整数范围内解 3a + 7b = 24
  1. 0≤7b≤24⇒b∈{0,1,2,3}\displaystyle 0 \le 7b \le 24 \Rightarrow b \in \{0,1,2,3\} b 乘的是较大的数,取值很少:7b 不能超过 24,所以 b 只能是 0、1、2 或 3。
  2. 24−7b≡0(mod3)  ⟺  b≡0(mod3)\displaystyle 24 - 7b \equiv 0 \pmod 3 \iff b \equiv 0 \pmod 3 用整除筛选:24 - 7b 必须是 3 的倍数。7 除以 3 余 1,24 除以 3 余 0,所以 b 必须是 3 的倍数。
  3. b∈{0,3}\displaystyle b \in \{0, 3\} 剩下 b = 0 和 b = 3。
  4. 3a=24⇒a=8\displaystyle 3a = 24 \Rightarrow a = 8 当 b = 0 时:3a = 24,所以 a = 8(八次 3 分)。
  5. 3a=3⇒a=1\displaystyle 3a = 3 \Rightarrow a = 1 当 b = 3 时:3a = 24 - 21 = 3,所以 a = 1(一次 3 分和三次 7 分)。
  6. 3⋅8=24,3+21=24\displaystyle 3\cdot 8 = 24,\quad 3 + 21 = 24 验证: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,这与整除证明中的归纳思想相同。

12131415161718+3+318 − 12 = 3 + 3 = 6
12、13、14 三个连续数可达后,每跳一次 3 就到达下一个同余的数:12 → 15 → 18,依此类推。

常见错误

  • 以为最大公约数为 1 就什么都能凑出。 它只保证超过某个值之后都可达,并不是每个数都可达。用 3 和 7 时,11 仍然不可能。
  • 允许负系数。 方程 3a+7b=13a + 7b = 1 有整数解(a=−2a = -2,b=1b = 1),但没有人能得到“负两个射门”。硬币问题要求系数非负。
  • 没有检查 b 的所有取值。 找到第一个解就停下会漏掉组合,24 分的例子就说明了这一点。
  • 把附加分当作独立得分。 它依附于达阵;单独计算会错误地得出 1 分可能出现的结论。

常见问题

橄榄球比赛能以 1 分结束吗?

不能。附加分只在达阵之后出现,而能单独得分的方式都至少 2 分。由于 2 和 3 能凑出所有从 2 开始的整数,唯一不可能的最终比分是 1。

什么是 Frobenius 数?

它是无法用给定数值的非负整数组合表示的最大整数。对于最大公约数为 1 的两个数 a 和 b,它等于 ab - a - b。对 3 和 7 来说是 11。

如果这些数有大于 1 的公约数呢?

那么只有最大公约数的倍数能达到。例如只有 4 分和 6 分时,任何奇数比分都不可能,也不存在最大的不可达数。

三个或更多数值有公式吗?

三个或更多数值没有通用的封闭公式,通常用算法或按余数分析,就像我们处理 2 和 3 那样。