复读 https://www.matrix67.com/blog/archives/6970
$9$ 个硬币,有一个假币。你有一个天平,可以告诉你哪边重或一样重。天平上可以放任意多枚硬币,问你至少几次保证知道哪个是假币。
假币一定比正常币轻一些。
两次就可以。这个问题大家小学五年级就在课本上看过了。
那假设这个天平离线了,两次称完之后才会告诉你两次的结果呢?为了方便描述,我们管这玩意叫“天平鸡”!
(你干嘛~~哈哈哎呦~~~)
在这种情况下,我们还能用两次称出来吗?
其实可以。
我们还是分成三组。第一次把第一组和第二组拿上去称。
第二次我们每组里都 随便拿两个,两侧各放一个。
这样每组里都恰好有一个在左边,一个在右边,一个没放。
这时就会发现,因为只有某一个硬币有问题,因此其他硬币的影响会抵消掉,所以我们可以只关心第一次有问题的那组里的硬币。
我们用更形象的方式来解释这件事:
我们可以用这样的方式表示分组情况。比如我们认定一行为一组。
每次称重我们可以知道假币在哪一行,或者在哪一列。两次称重即可得知假币位置。
这样未免太简单了。那如果说我们不知道是否有假币,这样还可以吗?每次天平共用 $3$ 种状态,称两次就是 $9$ 种,而如果说加上没有假币,我们就有 $10$ 种状态了,显然称两次无法确定。
那么把硬币数量减少到 $8$ 个呢?使用“天平鸡”两次能不能称出来?
这样就搞定了。
我们先换个形式,一道经典题:
我有 $9$ 组正常的硬币,但是刚刚不小心混进去了一组假币。每组硬币有 $10$ 个,每个正常的硬币是 $100$ 克,假币则是 $99$ 克。每组里面要么全是真的,要么全是假的。
现在我们用一台电子秤来称(即可以知道你放上去的硬币的精准重量,单位:克),每次不一定要把整组放上去,可以只拿一部分,或者不拿,问你几次找到假的那组。
实际上我们可以在第一组拿 $1$ 个,第二组拿 $2$ 个,以此类推。最后我们用 $\left(1 + 2 + 3 + \cdots + 10\right) \times 100$ 减掉实际的得数,结果就是假币那组的编号。比如称出来是 $5497$ 的话,假币就位于第三组。原理显然。
我们回到上上个问题。如果现在只有 $7$ 个硬币,但是可能没有假币,用“天平鸡”能两次称出来吗?
你没看错,是 $7$ 个。其实我直接告诉你,两次“天平鸡”称不出来!
首先,我们需要让前两次称的硬币数量一样,又刚好有两个缺口,那就只能:
这样摆了。但是这样我们没法让每个硬币都上称,而因为可能没有假币,所以这样就不知道没上称的那个硬币是假币还是真币。
另外一道趣题:
$9$ 个硬币,只有一个假币。假币比真币轻。有三架天平,其中一架是坏的(但你不知道哪个是坏的)。坏的天平会随机给出称量结果。最少称几次能保证找出那枚假币?
一个思考题:
证明:用 $k$ 次“天平鸡”能确定哪个是假币,或断言没有假币的硬币个数不能超过 $3^k - 1$ 且不能等于 $3^k - 2$。
两个答案均见原 Matrix67 的博客。