五千年(敝帚自珍)

主题:【原创】从两个经典智力趣题谈起(一) -- 丁坎

共:💬102 🌺203
全看分页树展 · 主题 跟帖
家园 【原创】从两个经典智力趣题谈起(四)(上)

从两个经典智力趣题谈起(四)(上)

关于称珍珠问题,前面给出了一个常规解法,现在讨论一下三进制思路下的扩展和通解。

这个题目是公认的经典智力趣题,涉及的内容又比较初等,按说解法应该已经被历代高手穷尽了。我在前几年搞出来一个通解,却好象不见有人提到过,我自己也一直没有公布,今天就在西西河说说吧。(万一的确没有人提过,请大家记得我的发明权,呵呵。如果有人提出过,请告诉我出处。)

上篇 来由篇(有思路,较长,没耐心的等下篇吧)

解出称三次分十二颗珍珠的问题后,一个很自然的问题是:

如果允许称四次,可以区分多少颗珍珠?

如果一时没有头绪,不妨退一步:

如果允许称二次,可以区分多少颗珍珠?

这个不费事,任何人稍加尝试都可以得出正确答案:三颗。

二次三颗,三次十二颗,这中间是什么关系?

首先回到我们的常规解法,可以发现两点:

1 多次根据一次称量的三种不同结果来区分三个可能的赝品

2 当第一次称量的八颗珍珠平衡时,剩下的四颗可以通过两次称量完成检测,而这,在单独的两次中是无法完成的。

这就给了我们两个启示:

1 三进制

2 进行称量的不同次数之间不应该分开考虑,而必须作为一个整体考虑。

在这个背景下,我们可以想到,每次称量可以提供三种结果,N次称量可以提供的可能性是3的

N次方。考察一下3的2次方9与可分辨数3,3的3次方27与可分辨数12之间的关系,不难求得

可分辨数= (3的N次方-3)/2

这个公式的涵义是什么呢?

赝品在每次称量时有三种可能:左盘,右盘,不选

反过来,这三种可能在赝品轻重确定的情况下,将直接确定天平的状态。

比如说,赝品重于真品,则赝品的

左盘,右盘,不选

直接确定天平的

左重,右重,平衡

若赝品轻于真品,则刚刚相反。

这时我们明白,几乎每一组天平测量结果都可以确定一个赝品及其轻重,尽管我们此时还不明白减3的涵义,但已经可以确定这种思路的正确性了。

有了思路之后,还要找出具体的执行方案,也希望在具体方案中找到减3的原因。

以称三次为例(呵呵,我当时就是直接硬求出来的,并没有想到求助于称两次),我的思路是:

A

分别以1,0,-1标记一颗珍珠在某次称量时的状态:左盘,不选,右盘

以一个三维数值矢量来标记某颗珍珠的三次称量称量,

如1,1,1 则表示这颗珍珠每次都被放入左盘。

共有27个可能的数值矢量。

以左,平,右标记天平的一次称量结果:左重,平衡,右重

(其实用1,0,-1是一样的,但我当时脑袋被折腾晕了,不想再费脑浆去转换,所以用了更直观的记法。)

以一个三维字符矢量来标记天平三次称量结果,

如左,左,左则表示天平三次称量结果都是左盘更重。

共有27种可能的字符矢量。

现在的问题是要用27个数值矢量去标记珍珠,以找出赝品,

让我们来看看,这种标记需要满足些什么条件:

首先,要区分一颗珍珠与另一颗珍珠,另一颗珍珠必须拥有不同的矢量,

否则无法根据三次测量结果来区分则两颗珍珠。

所以,12颗珍珠应该拥有彼此不同的数值矢量。

其次,如果两颗珍珠每次取用状态完全相反,则无法判断是此重还是彼轻,

所以,一旦一个数值矢量被选中,由它取反而得的矢量就该被排除

比如说1,0,1被选中,-1,0,-1就该被排除。否则当称量结果为左平左时,我们无法判断

是1,0,1重于真品,还是-1,0,-1轻于真品。

也就是说,除000外的26个数值矢量可以被分成互为取反的13对,每对只能有一个被选用。

其实分析到了这里,也就明白了减去000是必然的,因为一旦它被选用,就意味着某颗珍珠根本没有参与称量,如果它恰好是赝品,我们就无从知道它比真品重还是轻。

再次,被选用的12个数值矢量相加,总和必须是0,0,0,这是要求天平左右两盘的珍珠数必须相等,这样才能保证天平称量的重量差别是由赝品与珍品的重量差别迎起的,而不是由左盘3颗右盘4颗那样的数量差别引起的。

当时就根据这三条标准,再减去0,0,0,并连带的减去极端情况的思路,把1,1,1和-1,-1,-1减去,(其实这两个矢量可以不排除)从24个可能的数值矢量中凑出了满足三标准的12个矢量,从而得到一个解。

硬凑很久之后,终于得到一个解答,虽然颇有成就感,但也累得精疲力竭。

所以后来我又狠狠地思考了一番,是否有一种方便快捷的方法,无论称量次数是多少,都可以迅速求出一组解,很幸运地是,这种方法被我找到了。

呵呵,喝口水先。

(使用尽量中文 兄的思路和我很接近,只是我用 +1,-1 代表左右似乎更直观一些,在第二,三个条件的表达上

一旦一个数值矢量被选中,由它取反而得的矢量就该被排除

被选用的12个数值矢量相加,总和必须是0,0,0,

也比较好理解。

使用尽量中文 兄 直接使用三进制编码应该也有一些优越性,他在寻求12个数值矢量时就不再是纯粹的拼凑,而有一套固定的程序,可惜我看得不太懂,也无法确证它在数学上的正确性,

特别是称量次数较大的时候。)

全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河