天平找异重豆 II

Balanced Beans II

专题: Strategy / 策略
难度: L6
来源: QuantQuestion

个人笔记

题目详情

有 12 颗豆子，其中恰好 1 颗与其他不同，它可能略重也可能略轻。使用天平左右称重。

问：最少需要称几次，才能保证确定哪一颗是异常豆子并判断它是偏重还是偏轻？

英文原题

There are $12$ beans; one weighs slightly heavier or lighter than the others. What is the minimum number of times a balance scale must be used to guarantee the determination of the abnormal bean?

解析

最少需要 $\boxed{3}$ 次称重。

理由（信息论下界）：

每次称重有 3 种结果（左重/右重/平衡），3 次最多区分 $3^3=27$ 种情况。
12 颗豆子，每颗可能“偏重/偏轻”两种，共 $24$ 种可能，需要至少 3 次。

并且经典 12-coin 方案可在 3 次内完成，因此最小次数为 3。

英文解析

A minimum of $\boxed{3}$ weights is required.

Rationale (lower bound of information theory):

There are 3 results (left/right/balance) for each weighing, and a maximum of $3^3=27$ cases can be distinguished between the 3 weights.
12 beans, each of which may be "overweight/underweight", a total of $24$ possible, need at least 3 times.

And the classic 12-coin plan can be completed in 3 times, so the minimum number of times is 3.