天平找假币：三分法吊打二分

题目

有 $N$ 个外观相同的球，其中恰好一个较轻（其余等重）。用没有砝码的天平，最少几次称量必能找出那个轻球？

（例：27 个球，几次？）

答案与解析

用三分法，不是二分。每次把球分成三堆尽量均等，称其中两堆：

• 若平衡 → 轻球在第三堆；
• 若不平衡 → 轻球在翘起的那堆。

一次称量把“嫌疑范围”缩到约 $1/3$。所以 $k$ 次最多能从 $3^k$ 个球中找出轻球。

• 3 球：1 次（称 1 vs 1，平则余下，不平则翘起者）
• 9 球：2 次
• 27 球：3 次
• 一般：$N$ 球需 $\lceil \log_3 N\rceil$ 次

对比二分（每次缩到 1/2），三分利用天平的“三结果”（左重/右重/平衡），信息效率更高。

背后的数学

这是信息论的教科书案例：天平每次产生 $\log_2 3\approx1.585$ 比特，比硬币翻转的 1 比特更值钱。若不知假币轻重，则情况数翻倍（轻/重），需用 $\lceil\log_3(2N)\rceil$ 估算——著名“12 球 3 次”谜题正是这条边界上的精妙构造（参见 12 球称 3 次）。