称球问题 - 通解证明和方案构造

抖音上看到的面试题:

有 12 个外观一样的小球,只知道其中一个球的重量与其它球不同。用一个没有砝码的天平,最坏情况下最少要称几次,才能找到这个重量不一样的小球并确定它是偏轻还是偏重。

正确答案 3 次。

称球问题有很多变化,每次遇到,可能花点时间写写画画就能解决,就像上面这个方案一样,更多的是“灵光一现”,恰好“碰”到了答案。对于各种称球问题,我很好奇到底有没有套路可循。

维基百科给出了下面四类称球问题的通解。

已知条件 目标 称 $k$ 次最多能有几个球 有 $n$ 个球最坏情况下最少要称几次
有一个问题球,它偏轻或偏重 确定问题球 $3^k$ $\lceil log_3{n} \rceil$
有一个问题球,它的重量与其它球不同 确定问题球 $\cfrac{3^k - 1}{2}$ $\lceil log_3(2n + 1) \rceil$
有一个问题球,它的重量与其它球不同 确定问题球,并确定它是偏轻还是偏重 $\cfrac{3^k - 3}{2}$ $\lceil log_3(2n + 3) \rceil$
可能有一个问题球,它的重量与其它球不同 确定有没有问题球 $\cfrac{3^k - 3}{2}$ $\lceil log_3(2n + 3) \rceil$

如果你对为什么会是这样感兴趣,请继续阅读。接下来将证明这些结论,并介绍如何构造称球问题的通解方案。

发现

一个球在参与称量之前,它的状态是未知的:可能有问题,也可能没问题。如果某个球有问题,那么还对应两种可能:偏轻或偏重。

在天平两边各放相等数量的球称一次,如果平衡,那么天平上的所有球都正常,有问题的球在剩下的那堆球里。如果不平衡,那么剩下的那堆球都正常,有问题的球在这些参与称量的球里,假设此时天平左轻右重,那么只会是左边的某个球偏轻或右边的某个球偏重。也就是说,一个球在参与称量后,如果不能确定它是正常球,我们也至少能确定它是“可能偏轻”还是“可能偏重”。某个球一旦“上过天平”,就不会出现既“可能偏轻”又“可能偏重”的情况。

例如,称 ① ② 和 ③ ④ 结果天平左轻右重,那么我们能确定问题球在这四个球里,仅凭这个结果还不能确定具体哪三个球正常,但能确定如果 ① 或 ② 是问题球那它就只会偏轻,如果 ③ 或 ④ 是问题球那它就只会偏重。所以如果之后某次称球时又用到了 ① 并且天平放 ① 的那边更重,就可以确定 ① 一定是正常球,因为它如果是问题球就不可能偏重。

结论一

对 $n$ 个都“上过天平”的球,最坏情况下最少要称几次,才能确定问题球并能确定它是偏轻还是偏重?倒着想容易一些。

因为这里讨论的球都“上过天平”,所以只要能找到问题球,就等于确定了它是偏轻还是偏重

若 $n = 1$,显而易见,需要称 0 次。

若 $n = 2$,则需要称 1 次。此时有两种情况:(1)两个球状态相同,都“可能偏轻”或都“可能偏重”;(2)两个球一个“可能偏轻”另一个“可能偏重”。对于(1)直接把这两个球放到天平上称一次即可,谁更轻或更重则谁有问题。对于(2)则需要用到额外的一个正常球[注]:任意拿一个球跟正常球称一次,不平衡则这个球是问题球,平衡则另一个球是问题球,根据问题球在称之前的状态就可以确定它具体是偏轻还是偏重。所以不管怎样,都需要称 1 次。

若 $n = 3$,则需要称 1 次。此时至少有两个球状态一样,要么都“可能偏轻”,要么都“可能偏重”,直接把这两个状态一样的球放到天平上称一次即可。

若 $4 \le n \le 9$,很明显,称 1 次是不行的,用反证法很容易证明(有四个状态相同的球)。那称两次行不行?

我们将所有球尽可能的等分成 A、B、C 三堆,保证每堆球都不超过 3 个,且 A、B 两堆各有相同数量“可能偏轻”的球,也各有相同数量“可能偏重”的球。这总是可以做到的,先从“可能偏轻”的球中任意挑出 $2a$ 个球($a \ge 0$)均分成 A、B 两堆,再从“可能偏重”的球中任意挑出 $2b$ 个球($b \ge 0$)均分到 A、B 中来平衡三堆球的数量,以保证每堆球都不超过 3 个。即保证

$$\begin{cases} 1 \le a + b \le 3 \\[0.5em] 1 \le n - 2(a + b) \le 3 \end{cases}$$

将 A、B 两堆球放到天平上称一次。如果平衡,则 A、B 中的所有球都正常,有问题的球一定在 C 里,而 C 里最多 3 个球,根据之前的讨论再称一次就能确定问题球并确定它是偏轻还是偏重。如果 A 轻 B 重,则 A 中所有“可能偏重”的球、B 中所有“可能偏轻”的球和 C 中的所有球都正常,有问题的球只可能是 A 中“可能偏轻”的球或 B 中“可能偏重”的球,共有 $a + b$ 个也不大于 3,只需要再称一次。如果 A 重 B 轻,则 A 中所有“可能偏轻”的球、B 中所有“可能偏重”的球和 C 中的所有球都正常,有问题的球只可能是 A 中“可能偏重”的球或 B 中“可能偏轻”的球,共有 $b + a$ 个也不大于 3,也只需要再称一次。第一次称完后不论结果如何,都只需要再称一次。所以在 $4 \le n \le 9$ 时称 2 次就能确定问题球并能确定它是偏轻还是偏重。

注:按此方案分球,每次称球时如果平衡则能确定天平上的球都正常,如果不平衡则能确定剩下的球都正常。所以不论结果如何,称一次都能确定出至少一个正常球。也就是说,如果总共要称多次,那在最后一次称球时一定已经确定出了至少一个正常球,即额外需要一个正常球这个条件总是能被满足。

至此,我们可以得出结论:在 $n$ 个($n \ge 3$)都“上过天平”的球中确定问题球并确定它是偏轻还是偏重,最坏情况下最少要称 $\lceil log_3{n} \rceil$ 次。请注意,为了严谨,我们限制了 $n \ge 3$,这好像不太优雅,但我们可以反过来说:

称 $k$ 次($k \ge 1$),最坏情况下最多可以从 $3^k$ 个都“上过天平”的球中确定问题球并确定它是偏轻还是偏重。

这个结论用数学归纳法很好证明。

当 $k = 1$ 时,由上面的讨论可知,最多能从 3 个都“上过天平”的球中确定问题球并确定它是偏轻还是偏重,结论成立。

假设当 $k = i$($i > 1$)时,结论成立,最多可以有 $3^i$ 个都“上过天平”的球。

当 $k = i + 1$ 时,最多有 $3^{i+1}$ 个球,使用“三分法”,我们总是可以将这些球分成三堆,使每堆球都不超过 $3^i$ 个,并同时保证至少有两堆球各有相同数量“可能偏轻”的球,也各有相同数量“可能偏重”的球。此时,称 1 次就可以将问题转化为已经讨论过的情况,不论结果如何,根据假设,再称 $i$ 次就能确定问题球并确定它是偏轻还是偏重,所以总共需要称 $i + 1$ 次,当 $k = i + 1$ 时结论也成立。

由数学归纳法可知,当 $k \ge 1$ 时,结论成立。证毕。

结论二

额外给 1 个正常球,称 $k$ 次($k \ge 1$),最坏情况下最多可以从 $\cfrac{3^k + 1}{2}$ 个球中确定问题球,但会有且只有一种情况无法确定它是偏轻还是偏重。

如果是 1 个球,直接拿它跟正常球称 1 次就可以得出结论。

如果是 2 个球,任选一个球跟正常球称 1 次,如果不平衡则找到了问题球并能确定它是偏轻还是偏重;如果平衡则另一个球是问题球,这是结论中仅有的一种情况,我们只能通过“排除”法确定问题球,但无法确定它是偏轻还是偏重。

如果是 3 个球,很明显,称 1 次在最坏情况下无法确定问题球,不论是两边各放一个球还是两边各放两个球(额外还有 1 个正常球)。

所以当 $k = 1$ 时,最坏情况下最多可以从 2 个球中找到问题球,有且只有一种情况无法确定它是偏轻还是偏重,结论成立。

假设当 $k = i$($i > 1$)时,结论成立,最多可以有 $\cfrac{3^i + 1}{2}$ 个球,有且只有一种情况无法确定它是偏轻还是偏重。

当 $k = i + 1$ 时,最多有 $\cfrac{3^{i+1} + 1}{2}$ 个球。考虑第一次称球,天平一边放 $\cfrac{3^i + 1}{2}$ 个球,另一边放 $\cfrac{3^i - 1}{2}$ 个球和 1 个已知的正常球。

$$\frac{3^i + 1}{2} = \frac{3^i - 1}{2} + 1$$

如果不平衡,根据结论一,都“上过天平”的 $\cfrac{3^i + 1}{2} + \cfrac{3^i - 1}{2} = 3^i$ 个球只要称 $i$ 次,就能找到问题球并确定它是偏轻还是偏重。如果平衡,那么问题球在剩下的那堆球中,最多 $\cfrac{3^{i+1} + 1}{2} - 3^i = \cfrac{3^i + 1}{2}$ 个,此时已经有 $3^i$ 个正常球了,根据假设,也只要再称 $i$ 次就能确定问题球,但会有且只有一种情况无法确定它是偏轻还是偏重。所以不论第一次称球结果如何,都只需要再称 $i$ 次,总共要称 $i + 1$ 次,当 $k = i + 1$ 时结论也成立。

由数学归纳法可知,当 $k \ge 1$ 时,结论成立。证毕。

那为什么会有一种情况无法确定问题球是偏轻还是偏重呢?

如果是 2 个球称 1 次:

  • 称 ① 和额外的正常球:
    • 不平衡,则确定 ① 是问题球并能确定它是偏轻还是偏重
    • 平衡,则“排除”出 ② 是问题球,但无法确定它是偏轻还是偏重

如果是 5 个球称 2 次:

  • 称 ①、② 和 ③、正常球
    • 不平衡,根据结论一再称一次就能从 ① ② ③ 中确定问题球并确定它是偏轻还是偏重
    • 平衡,称 ④ 和正常球
      • 不平衡,则确定 ④ 是问题球并能确定它是偏轻还是偏重
      • 平衡,则“排除”出 ⑤ 是问题球,但无法确定它是偏轻还是偏重

看到没,最后那个球一直被“剩下”从来都没“上过天平”,我们自始至终都没用到这个球,它有问题是被每次天平都平衡“排除”出来的,有没有它对具体怎么称球都没有影响。在所有可能的称球结果中,有且只有这一种情况,我们只能用“排除法”确定出问题球但无法知道它是偏轻还是偏重。

那如果需要确定问题球并确定它是偏轻还是偏重,怎么办?没有这个球,不就可以了?😂

额外给 1 个正常球,称 $k$ 次($k \ge 1$),最坏情况下最多可以从 $\cfrac{3^k - 1}{2}$ 个球中确定问题球并确定它是偏轻还是偏重。

结论

讨论到现在好像都没解决问题,但细品后你会发现,不论第一次怎么称球,称完后的局面都会变成结论一或结论二中的情况

有 $n$ 个球($n \ge 3$),在天平两边各放 $p$ 个球称一次($p \ge 1$),还剩下 $q$ 个球没有称($q \ge 0$)。如果平衡则这 $2p$ 个球是正常球,问题球在剩下的 $q$ 个球中:用结论二可解;如果不平衡则剩下的 $q$ 个球是正常球,问题球在这 $2p$ 个球中,它们都是“上过天平”的球:用结论一可解。

所以为了保证方案在最坏情况下称的次数最少,我们只要让这两个结果“分支”所需的称球次数都尽可能少就可以。假设总共要称 $k$ 次来确定问题球并确定它是偏轻还是偏重,对第一次称球,如果:

  • 不平衡,根据结论一,再称 $k-1$ 次在最坏情况下最多可以有 $3^{k-1}$ 个都“上过天平”的球。但 $3^{k-1}$ 是个奇数,而每次拿到天平两边称的球加一起肯定是偶数个,所以这个分支实际最多可以有 $3^{k-1} - 1$ 个球
  • 平衡,则能确定天平上的都是正常球,至少有 1 个,根据结论二,剩下的球最多可以有 $\cfrac{3^{k-1} - 1}{2}$ 个

因此最多共可以有 $3^{k-1} - 1 + \cfrac{3^{k-1} - 1}{2} = \cfrac{3^k - 3}{2}$ 个球。

称 $k$ 次($k \ge 1$),最坏情况下最多可以从 $\cfrac{3^k - 3}{2}$ 个球中确定问题球并确定它是偏轻还是偏重。

如果只需要找到问题球而不用确定它是偏轻还是偏重呢?

那平衡“分支”里可以多一个球。每次称球天平都平衡,这个多出来的球会被“排除”成问题球,因为从没“上过天平”所以无法确定它是偏轻还是偏重,也就是结论二中描述的那种仅有的情况。所以此时最多共可以有 $3^{k-1} - 1 + \cfrac{3^{k-1} + 1}{2} = \cfrac{3^k - 1}{2}$ 个球。

称 $k$ 次($k \ge 1$),最坏情况下最多可以从 $\cfrac{3^k - 1}{2}$ 个球中确定问题球,但会有且只有一种情况无法确定它是偏轻还是偏重。

至此,我们详细说明了二、三两种类型称球问题的通解,并证明了结论。

对于类型一的称球问题,已知问题球是偏轻或偏重实际上相当于把所有球都变成了“上过天平”的球,它们的状态只会是都“可能偏轻”或都“可能偏重”,所以能直接使用结论一:称 $k$ 次最多可以有 $3^k$ 个球。

对于类型四的称球问题,可能有一个问题球需要确定有没有,实际上跟类型三是完全等价的。为什么只找到问题球不行还要能确定它是偏轻还是偏重?或者说,为什么称 $k$ 次最多不能是 $\cfrac{3^k - 1}{2}$ 个球?因为如果称球时出现了结论中描述的那种仅有的情况,天平一直平衡,就无法确定最后剩下的球是什么状态,这时候不能用“排除法”因为我们事先不知道这堆球里到底有没有问题球。或者说,如果多出来这么个球,就会有一种情况无法确定这堆球里到底有没有问题球,所以不能有这个球:称 $k$ 次最多可以有 $\cfrac{3^k - 3}{2}$ 个球。

通解方案

上面这些结论的证明都是构造性的,以此为据,可以很容易的写出通解方案。让我们还以 12 个球为例,重新设计方案,称 3 次(绿色、蓝色、红色)从这堆球中确定问题球并确定它是偏轻还是偏重。

根据结论一,第一次要称 $3^2 - 1 = 8$ 个球,称 ① ② ③ ④ 和 ⑤ ⑥ ⑦ ⑧,如果

  • 左轻右重,则 ⑨ ⑩ ⑪ ⑫ 是正常球,① ② ③ ④ “可能偏轻”,⑤ ⑥ ⑦ ⑧ “可能偏重”。把这 8 个球分成三堆各 3、3、2 个球,每堆都不超过 3 个,前两堆各有两个球“可能偏轻”一个球“可能偏重”,称 ① ② ⑤ 和 ③ ④ ⑥
    • 左轻右重,则 ③ ④ ⑤ ⑦ ⑧ 是正常球,① ② “可能偏轻”,⑥ “可能偏重”,称 ① 和 ②
      • 左轻右重,则 ① 是问题球,偏轻
      • 左重右轻,则 ② 是问题球,偏轻
      • 平衡,则 ⑥ 是问题球,偏重
    • 左重右轻,则 ① ② ⑥ ⑦ ⑧ 是正常球,③ ④ “可能偏轻”,⑤ “可能偏重”,称 ③ 和 ④
      • 左轻右重,则 ③ 是问题球,偏轻
      • 左重右轻,则 ④ 是问题球,偏轻
      • 平衡,则 ⑤ 是问题球,偏重
    • 平衡,则 ① ~ ⑥ 是正常球,⑦ ⑧ “可能偏重”,称 ⑦ 和 ⑧
      • 左轻右重,则 ⑧ 是问题球,偏重
      • 左重右轻,则 ⑦ 是问题球,偏重
      • 平衡,不可能出现这种结果
  • 左重右轻,则 ⑨ ⑩ ⑪ ⑫ 是正常球,① ② ③ ④ “可能偏重”,⑤ ⑥ ⑦ ⑧ “可能偏轻”。跟左轻右重实际等价,称 ① ② ⑤ 和 ③ ④ ⑥
  • 平衡,则 ① ~ ⑧ 是正常球,在 ⑨ ⑩ ⑪ ⑫ 里确定问题球并确定它是偏轻还是偏重,需要称 2 次。根据结论二,一边放 $\cfrac{3^1 + 1}{2} = 2$ 个球,另一边放 1 个球和额外的 1 个正常球,称 ⑨ ⑩ 和 ⑪ ①
    • 左轻右重,则 ⑫ 是正常球,⑨ ⑩ “可能偏轻”,⑪ “可能偏重”,称 ⑨ 和 ⑩
      • 左轻右重,则 ⑨ 是问题球,偏轻
      • 左重右轻,则 ⑩ 是问题球,偏轻
      • 平衡,则 ⑪ 是问题球,偏重
    • 左重右轻,则 ⑫ 是正常球,⑨ ⑩ “可能偏重”,⑪ “可能偏轻”。跟左轻右重实际等价,称 ⑨ 和 ⑩
    • 平衡,则 ⑨ ⑩ ⑪ 是正常球,⑫ 被“排除”成问题球但不确定它是偏轻还是偏重,称 ⑫ 和 ①
      • 左轻右重,则 ⑫ 是问题球,偏轻
      • 左重右轻,则 ⑫ 是问题球,偏重
      • 平衡,不可能出现这种结果

最后留一道经典题给你思考。称 3 次最多能从 13 个球中确定问题球,但会有一种情况无法确定问题球是偏轻还是偏重,要怎么设计称球方案?如果额外给 1 个正常球,又该如何设计称球方案才能从这 13 个球中确定问题球并确定它是偏轻还是偏重?欢迎在评论区里言。😊

参考