小学数学题中的天眼4:复杂三进制

上上篇我们介绍了2进制。

上一篇我们用三进制来检验进制思维，最后有一道附加题。

今天我们来挑战它，看是否真的理解了三进制。同时我们再渗透一点信息论，为最后一篇继续做铺垫。

题目：有8个小球，其中一个球重量和其余的不同，但是不知道是偏重还是偏轻，还是用无砝码的天平称，运气最坏的情况下，最少需要多少次才能找出这个球？ 

为了增加趣味性，我们可以把球比喻为人，重量不同的目标球为嫌疑犯，体重和其他人都不一样。如何抓他出来呢？

先复习前一篇知识点：

老鼠毒酒问题：老鼠只有2 种结局（死 / 活）→二进制；每测一次，有 2种输出。称 k 次，总共有2^k种不同结果。

天平问题：3 种结局（左重 / 右重/ 平衡）→三进制：每称一次，有 3 种输出。称 k 次，总共有3^k种不同结果。

当能够输出的不同结果数多于我们需要排查的可能性时，问题就有解了。

拆解本题目：

目标球不知道是偏重还是偏轻，所以，总共有多少种可能性呢？

先让孩子思考一下，^_^

答案是，2*8=16种。

那么，最坏运气时，最少我们需要多少次测试呢？

• 3^2=9，能分辨 9 种情况，9 < 16， 2次不行。
• 3^3=27，能分辨 27 种情况，27 > 16，3次应该够了。

具体怎么称球（“嫌疑犯分组审讯”）：

给 8 个球按顺序编号：①②③④⑤⑥⑦⑧

第 1 次：左①②③ vs 右④⑤⑥ （⑦⑧先放边上）

            情况 A：天平平衡了！

→ 坏蛋在⑦⑧里，而且①~⑥都是好人（正常球）！

·第 2 次：⑦ vs ①（好人）

o如果不平衡，不管⑦重或轻→⑦就是坏蛋。2 次就抓到了（运气好）。

o如果平衡，⑦不是坏蛋（因为①是好人）。那么→⑧是坏蛋。2 次就抓到了（运气好）。

            情况 B：①②③重，④⑤⑥轻

（本文主干都在情况B下面，一直等到末尾，才会看到居中的情况C：①②③轻，④⑤⑥重，而且其分析思路同情况B，不再具体展开）

→ 坏蛋就在①~⑥里。而且这时候我们得到了非常重要的线索：

①②③（原本重的一侧）其中一个只能是偏重；

④⑤⑥（原本轻的一侧）其中一个只能是偏轻；

⑦⑧（没上过秤）是好人（因为坏人已经明确在①~⑥里面了）。

第2 次：①④ vs ②⑤（⑦⑧是好人，在旁边休息）

为什么要这样组合？因为我们要看天平往哪边倒，来排除嫌疑人。

故意把“可能重的”和“可能轻的”混着称，才可以尽可能的均分3个输出分支（非常重要，见下面紫色字体的解释）。

这一步是本题的难点，可能发生比较多的错误。

第一种 错误类型 ：以①② vs ④⑤为例：

·左盘重：可能性为4

左盘①②：这两人之一如果坏，都只会让左边重

右盘④⑤：这两人之一如果坏，都只会让右边轻（也就是左边重）

4 种完全不同的可能真相，全都指向同一个“左边重”！按这样的称法， 第三次称量根本没法从 4 个人里揪出 1 个（3^1=3，一次最多分3种可能哦）。需要第四次称才能完成。

·右盘重：可能性为0

·平衡：可能性为0

总结：这种称法，3种输出分别产生了：左重4，右重0，平衡0。显然，没有充分利用右重和平衡这两个输出分支。而对于左重4，需要再称两次才能分出，实验失败。

还有更多的“同类型放一起”放一起的错误组合

（可以让孩子思考一下，还有哪些）：

比如：

• ①③ vs ④⑤、②③ vs ④⑤
• ①② vs ④⑥、①② vs ⑤⑥
• ①③ vs ④⑥、①③ vs ⑤⑥
• ②③ vs ④⑥、②③ vs ⑤⑥

第二种错误类型：以① vs ②为例：

·①偏重→左边重（锁定①）

·②偏重→右边重（锁定②）

·但假如是平衡呢？余下的③④⑤⑥全都没上秤。也就是余下的有 4种可能待排查（③重、④轻、⑤轻、⑥轻），靠第三次绝对分不出来（3^1=3，一次最多分3种可能哦）。

·类似的错误类型举例：

① vs ④①重和④轻都会导致“左边重”，剩下4 种全进平衡

① vs ⑦（好人）①重→左重，剩下5 种 全进平衡，更惨

④ vs ⑤④轻→右重，⑤轻→左重，剩下4 种全进平衡

小结

    既然“重球”会让所在侧下沉，“轻球”会让所在侧上浮，那就需要把一个重嫌疑和一个轻嫌疑放在同一侧，（嫌疑犯只有一个，重嫌疑和轻嫌疑不可能同时出现；那么，当被安排在同一侧的时候，下沉或上翘就能够对应地指出是重嫌疑还是轻嫌疑是真的）。

回到正确的思路：情况B,第2次称： ①④ vs ②⑤（⑦⑧是好人，在旁边休息）

·左盘：①（可能重，或正常），④（可能轻，或正常）

o如果①坏→左盘下沉（左重）

o如果④坏→左盘上翘（左轻，即右重）

充分利用了左盘这个分支。

·右盘：②（可能重）+ ⑤（可能轻）

o如果②坏→右盘下沉（右重，即左轻）

o如果⑤坏→右盘上翘（右轻，即左重）

充分利用了右盘这个分支。

·平衡：①④ ②⑤都正常

o余下的③偏重，或者：

o余下的⑥偏轻

充分利用了平衡这个分支。

重点：上述三个输出分支的结果，每个只对应2 种 可能。第三次随便拿一个好人球一比就能定案。

还有哪些正确的搭配呢？

只要满足这个原则：左盘 = 1 个重嫌疑+ 1 个轻嫌疑，右盘 = 剩下的 1 个重嫌疑 + 1 个轻嫌疑，就都是正确的。比如：

你会发现规律：左盘和右盘必须“交叉混搭”，绝不能把两个重嫌疑或两个轻嫌疑放在同一侧。

其实也可以用好人球，比如 ①④ vs ②⑦（⑦是已知好人）：

·左重：①重（1 种）

·右重：②重或④轻（2 种）

·平衡：③重、⑤轻、⑥轻（3 种）

第三次称量时，如果碰到平衡（3 种可能），你可以称⑤ vs ⑥：

·左重→⑥轻

·右重→⑤轻

·平衡→③重

这样也能 3 次解决，但第二次称的3个输出分支的结果可能分布是1:2:3，不如2:2:2来得对称、稳健。在“最坏情况”的语境下，我们追求的是无论运气多差都能保证破案，所以 2:2:2 的均衡方案才是最理想的答案。

            情况C：①②③轻，④⑤⑥重

分析思路同情况B，不再具体展开。

总结：

错误方案：

把“同类型的嫌疑人”放在同一侧导致效应叠加（4 种真相挤成一个结果），或者只让 2 个人上场，导致剩下 4~5 个人全堆在“平衡”那个分支里。

正确方案：

每个盘必须同时放一个“可能重的”和一个“可能轻的”，让他们互相拆台，这样三种结果才能各管 2 种可能性，第三次一锤定音。

也就是：3个输出分支尽可能均分，各自产生2种或不高于3种的可能性。

更多解释看下一篇信息论的极小极大思维。