算法合集之《猜数问题的研究》.doc

猜数问题的研究
第页共NUMPAGES21页
猜数问题的研究

上海市复旦附中高二(8)张宁

摘要：
在逻辑推理中有一类比较特殊的问题——“思维嵌套”问题，即在C的脑海中要考虑B是如何思考A的想法。对于这种问题通常非常抽象，考虑情况又十分繁多，思想极其复杂，用一般方法分析效果极差。本文以一个典型的“思维嵌套”问题——猜数问题为出发点，用一种新的方法从问题本质入手分析，很好的解决了问题，并阐述了新思路的优越性。由本质入手分析，避免了表面上的“思维嵌套”，且总结出了许多结论，使得解决问题的效率大幅度上升。在新思路的指引下将原问题向更普遍的情形推广，虽然问题变得更为繁琐复杂，但是由于把握住问题的命脉，有效地解决了问题。
关键字：推理，思维嵌套，终结情形，一类情形，二类情形，分组

正文：
一、问题原形
问题描述：
一位逻辑学教授有三名非常善于推理且精于心算的学生A，B和C。有一天,教授给他们三人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个大于0的整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。
教授轮流向A，B和C发问：是否能够猜出自己头上的数。经过若干次的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。
我们的问题就是：证明是否一定有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数，分析整个推理的过程，并总结出结论。
我们先分析一个简单的例子，观察每个人是如何进行推理的。
假设A，B和C三人，头上的数分别是1，2和3。
先问A
这时，A能看见B，C两人头上的数分别是2，3。A会发现自己头上只可能为3+2=5，或者3-2=1。可到底是1还是5，A无法判断，所以只能回答“不能”。
再问B
B会发现自己头上只可能为3+1=4，或者3-1=2。可到底是2还是4，B只能从A的回答中入手分析：（以下为B脑中的分析）
如果自己头上是2。则A能看见B，C两人头上的数分别是2，3，A会发现自己头上只可能为3+2=5，或者3-2=1。到底是1还是5，A无法判断，只能回答“不能”。这与A实际的回答相同，并不矛盾，所以B无法排除这种情况。
如果自己头上是4。则A能看见B，C两人头上的数分别是4，3，A会发现自己头上只可能为4+3=7，或者4-3=1。到底是1还是7，A无法判断，只能回答“不能”。这也与A实际的回答相同，并不矛盾，所以B也无法排除这种情况。
B无法判断，只能回答“不能”。
再问C
C会发现自己头上只可能为2+1=3，或者2-1=1。可到底是1还是3，C只能从A或B的回答中入手分析：（以下为C脑中的分析）
如果自己头上是1。
A会发现自己头上只可能为2+1=3，或者2-1=1。可到底是1还是3，是无法判断的，只能回答“不能”。这与A实际的回答相同，并不矛盾。
B会发现自己头上只可能为1+1=2（因为B头上是大于0的整数，所以B头上不能是1-1=0）。B应回答“能”。但这与B实际的回答矛盾。C能以此排除头上是1这种情况。
如果继续分析C头上是3这种情况会发现毫无矛盾（因为与实际情况相符）。
C将准确判断头上的数是3，所以回答“能”。
所以在第三次提问时有人猜出头上的数。

我们从每个人的角度出发，分析了头上数是1，2和3的情况。这种方法也是我们解决简单的逻辑推理问题所采用的普遍做法。但如果将问题的规模变大，会发现问题的复杂程度会急剧上升，几乎是多一次推理，问题的复杂度就要变大一倍。更复杂的例子，限于篇幅就不举了，但复杂程度是可以想见的。
靠如此烦琐的推理是不能很好解决问题的。原因在于有大量的“思维嵌套”，即：在C的脑海中要考虑B是如何思考A的想法。此外，这种方法不能够推导出有普遍意义的结论。让我们换一种思路来解决问题。
定义：
下面我们用第一位、第二位、第三位学生分别表示A，B，C三人
定义1：用四元组，，来描述推理过程中的一种情形，其中三个人头上数分别为，从第一位学生开始提问，且当前的被提问者为第k位学生。
性质：对于四元组，第k位学生可以不依靠别人的回答进行推理，能够直接判断出自己头上数，并称四元组描述的情形为“终结情形”。
性质：对于四元组，，并称四元组描述的情形为“一类情形”。
性质：对于四元组，,并称四元组描述的情形为“二类情形”。
定义2：集合。
定义3：集合。
定义4：集合。
定义5：若对于四元组
若第k位学生不能够猜出头上的数，记。
若第k位学生能够猜出头上的数，记为从第一位学生开始提问直到猜出头上的数的过程中总共的提问次数。
定义6：对于四元组，记（表示真或假），，表示当三位学生头上的数分别为，第k位学生是否在恰在第R次提问时