思维训练

两道相关的智力题

2008年12月9日 阅读(19)

大卫.希尔伯特说过,we must konw,we will know.

1.
一对夫妇邀请N-1对夫妇参加聚会(因此聚会上总共有2N人)。每个人都和所有自己不认识的人握了一次手。然后,男主人问其余所有人(共2N-1个人)各自都握了几次手,得到的答案全部都不一样。假设每个人都认识自己的配偶,那么女主人握了几次手?

答案:

首先每个人最大可能握手人数为,2N-2,所以取值范围为{0,1……2n-2},里面只有2n-1个数,又2N-1个人握手次数全部不同,可知它们的握手次数必然为0,1,2,3……2n-2.

其次,继续分析这个握手次数的集合,对于2n-2来说,不跟他握手的只有两个人,一个是他自身,另一个是它对象,可知0必然是它对象,因为如果不是,则2n-2将有三个人未与它握手,矛盾。

依次,往下,看1和2n-3,首先1必然与2n-2握了手,这样它肯定没有与2n-3握,而2n-3没有握的就包括了自身,0,1,如果1号不是它对象,那么会得到4个没有与它握手的,同样矛盾,所以1号必然是它对象。

同理往下,可以发现,(0,2n-2) (1,2n-3)(2,2n-4)…形成了一对,这样剩下的那个n-1就是男主人的老婆了。

再加个问题,那么男主人握了多少次手呢?

2.你在一幢100层大楼下,有21根电线线头标有数字1..21。这些电线一直延伸到大楼楼顶,楼顶的线头处标有字母A..U。你不知道下面的数字和上面的字母的对应关系。你有一个电池,一个灯泡,和许多很短的电线。如何只上下楼一次就能确定电线线头的对应关系?

答案:

之所以放在一块,是因为我意外的发现,其实这两个问题是有联系的。对于第一个问题,其实可以看成一个图,人是节点,而握手关系则形成了一条边,每个人握手次数则是节点的度。

那么它们有什么关系呢?

是的,这个问题我们可以构造一个类似问题1的图结构,这个图最好能满足,图中n个节点度各不相同,这样我们便可以首先在楼底下把各个线头连接(实际上就是图中的边),然后跑到楼顶测试各个点的度(选择一个点,枚举其他点,如果灯泡亮,说明两者右边,亮的次数就是该点的度)。

当然如果能够构造出一个这样的图,我们就可以只上楼就可以搞定了,连下楼都省了。问题是这样的图可以构造出来吗?我的感觉是不可以,因为类似与问题1,节点的度可选的只有{0,1,2……n-1},但是0和n-1是不能共存的。

但是我们可以构造出一个具有n-1个不同的度,其中两个可以具有相同的度,这样实际上就是问题1的情况了,(可以知道男主人必然与其中的一人握手人数相同)。这样问题就解决了。 

当然这个问题,还有其他解法,下面的解法是matrix67给出的,思路也很赞,而且感觉跟某道经典题类似。

下面把2,3连在一起,把4到6全连在一起,把7到10全连在一起,等等,这样你就把电线分成了6个“等价类”,大小分别为1, 2, 3, 4, 5, 6。然后到楼顶,测出哪根线和其它所有电线都不相连,哪些线和另外一根相连,哪些线和另外两根相连,等等,从而确定出字母A..U各属于哪个等价类。现在,把每个等价类中的第一个字母连在一起,形成一个大小为6的新等价类;再把后5个等价类中的第二个字母连在一起,形成一个大小为5的新等价类;以此类推。回到楼下,把新的等价类区别出来。这样,你就知道了每个数字对应了哪一个原等价类的第几个字母,从而解决问题。

又出现了一种解法,bbs上hwpo给出的:先将将楼下的先头两两连接1-2 3-4 …19-20 21
然后上楼测试也可以得到两两连接状态 不妨假设A-B C-D … S-T U
这样21对应U,然后将楼上的先头重排,可以排成这样 A B-C D-E … T-U
然后到楼下测试 此时和21一组的必定对应T 假定是6,那么5必定就对应S,一次类推

一开始我觉得这个方法不对,实际上是对的,主要思想是分组,在下面的时候我们可以按照

(1,2) (3,4)…….(19,20) 21分好组,上楼后我们可以找到那个是21,然后在这样连假设21是U,同时我们还能知道A跟谁连,B跟谁连,C跟谁连。假设(A B)(CD)…U,然后把它们这样连A    (B,C)…..(T,U),下楼后我们就能找到跟21连的是哪个了,比如如果是18,则T就是18,那么S就是17,因为第一次{17,18}{S,T}在一块,如果T是18那么S就是17啦。依次类推。

再加上我根据上面这个方法的提出的一个改进方法,这样就4个方法了,^o^:

实际上我还可以把它进一步简化,利用这样一个性质:

在楼下这样连(1-2-3-4……-20)  21

到楼上我们可以知道那个是21了,然后我们还可以测出这样一个序列来,首先找到只有度为1的那个,当然可能是1或20,然后然后找出与它相连的那个,这样逐步建立起一条链,但是我们不知道这条链的方向即可能是1-2-3…-20也可能是20-19-18….-1,这样也就是说我们只要找到链头到底是谁就好了,这样我们只要把21与某个头链接,下来再测一下就知道头是那个了。

比如我们在下面实际上的链是1-2-3-4-5…20,到了楼上我们得到一条链A-B-F-E-M…,同时我们知道21是U,那么只要将U与A相连,下来就知道A是1还是20了,这样就排好了这条链,同时对应关系也确定了。

You Might Also Like

No Comments

Leave a Reply