称量3次最多可以从多少个球中找到1个次品？

问题描述

这是一个经典的信息论与逻辑推理问题。我们需要通过一架没有刻度的天平，用最少的次数找出重量异常的次品球。

解决这个问题的核心在于将“不确定性”在天平的三种状态（左重、右重、平衡）间进行均摊，从而利用不等式求出最大可处理的小球数量。

        N： 小球总数。
k： 称量次数。
可能性总数： 由于每个球都可能偏轻或偏重，初始总情况为 \( 2N \) 种。
单次称量贡献： 天平有左重、右重、平衡 3 种结果，每次称量最多能将不确定性压缩为原来的 \( 1/3 \)。

    

假设第一次称量将 \( N \) 个球分为三堆：左盘 \( a \) 个，右盘 \( a \) 个，场外 \( b \) 个。即满足：

\[ N = 2a + b \]

此时已知盘内的 \( 2a \) 个球全是好球。次品的可能性剩下 \( 2b \) 种（\( b \) 个球各有两个状态）。剩下的 \( k-1 \) 次称量必须能覆盖这 \( 2b \) 种情况，故需满足：

2b \leq 3^{k-1} - 1

由于 \( 3^{k-1} - 1 \) 永远是偶数，为了保证 \( b \) 为整数，我们得到上限：

b \leq \frac{3^{k-1} - 1}{2} \quad \dots(1)

此时已知场外的 \( b \) 个球全是好球。若左重，则可能是左侧 \( a \) 个球中有重的，或右侧 \( a \) 个球中有轻的，共 \( a+a=2a \) 种可能性。同理，剩下的 \( k-1 \) 次称量必须覆盖这 \( 2a \) 种情况：

2a \leq 3^{k-1} - 1

同样进行整数化处理：

a \leq \frac{3^{k-1} - 1}{2} \quad \dots(2)

将（式1）和（式2）代入 \( N = 2a + b \)：

N = 2 \times \frac{3^{k-1} - 1}{2} + \frac{3^{k-1} - 1}{2}

N \leq \frac{2(3^{k-1} - 1) + (3^{k-1} - 1)}{2} = \frac{3 \times 3^{k-1} - 3}{2}

最终得到通用公式：

\[ N \leq \frac{3^k - 3}{2} \]

当称量次数 \( k=3 \) 时，我们可以计算出最大球数：

N \leq \frac{3^3 - 3}{2} = \frac{27 - 3}{2} = 12

这证明了 3次称量 最多可以从 12个 不知轻重的球中找到那个次品。