抖音上看到的面试题:
有 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 = 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 个球,直接拿它跟正常球称 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 次:
- 称 ①、② 和 ③、正常球
- 不平衡,根据结论一再称一次就能从 ① ② ③ 中确定问题球并确定它是偏轻还是偏重
- 平衡,称 ④ 和正常球
- 不平衡,则确定 ④ 是问题球并能确定它是偏轻还是偏重
- 平衡,则“排除”出 ⑤ 是问题球,但无法确定它是偏轻还是偏重
看到没,最后那个球一直被“剩下”从来都没“上过天平”,我们自始至终都没用到这个球,它有问题是被每次天平都平衡“排除”出来的,有没有它对具体怎么称球都没有影响。在所有可能的称球结果中,有且只有这一种情况,我们只能用“排除法”确定出问题球但无法知道它是偏轻还是偏重。
那如果需要确定问题球并确定它是偏轻还是偏重,怎么办?没有这个球,不就可以了?😂
结论
讨论到现在好像都没解决问题,但细品后你会发现,不论第一次怎么称球,称完后的局面都会变成结论一或结论二中的情况。
有 $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}$ 个球。
如果只需要找到问题球而不用确定它是偏轻还是偏重呢?
那平衡“分支”里可以多一个球。每次称球天平都平衡,这个多出来的球会被“排除”成问题球,因为从没“上过天平”所以无法确定它是偏轻还是偏重,也就是结论二中描述的那种仅有的情况。所以此时最多共可以有 $3^{k-1} - 1 + \cfrac{3^{k-1} + 1}{2} = \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 个球中确定问题球并确定它是偏轻还是偏重?欢迎在评论区里言。😊