Article Index

真假硬币王

Published on

复读 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 的博客。


No comments

Post a comment