上海复旦大学附属中学  张宁

【目的和思路】

　　 研究典型的“思维嵌套”问题——猜数问题，从问题的本质入手分析，避免了表面上的“思维嵌套”，使得解决问题的效率大幅度上升。

　　【制作过程】

　　首先对问题的原形产生了浓厚的兴趣，经过一系列深入的思考，将描述性的解决过程表达为严格的数学证明，同时也发现了问题可以继续推广，结合计算机来辅助研究，将问题两次推广，并最终较为圆满地解决了问题。

　　【科学性】

　　采用了严格的数学方法，经过详细的讨论得出了一系列结论。

　　【先进性】

　　采用初等数学的手段来研究一个规模化的逻辑推理问题，采用的证明方法也具有相当的创造性。

　　【实用性】

　　这类问题在数理逻辑和计算机科学中有较大的意义，这种解决逻辑推理问题的新思路，将会对这一类问题的解决产生影响。

　　【创新点】

　　摒弃了考虑逻辑推理问题的常规思路，从“思维嵌套”问题的本质入手分析，并证明了数个重要结论，并且在证明过程中，采用了多元数组及分组等概念来描述推理过程中的情形，并采用记号将抽象的推理过程用数学加以证明，在理论上有一个飞跃。

　　在逻辑推理中有一类比较特殊的问题——“思维嵌套”问题，即在C的脑海中要考虑B是如何思考A的想法。这种问题通常非常抽象，考虑情况又十分繁多，思想过程极其复杂，用一般方法分析效果极差。

　　一、问题原形

　　一位逻辑学教授有三名善于推理且精于心算的学生A，B和C。有一天教授给他们三人出了一道题：教授在每个人的脑门上贴了一张纸条并告诉他们，每个人的纸条都写了一个大于0的整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。

　　教授轮流向A，B和C发问：是否能够猜出自己头上的数。经过若干次的提问之后，当教授再次询问某人时，他突然露出了得意的笑容，把贴在自己头上的那个数准确无误地报了出来。

　　我们的问题就是：证明是否有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数。

　　我们先分析一个简单的例子，观察每个人是如何进行推理的。

　　假设A，B和C三人，头上的数分别是l，2和3。

　　l. 先问A

　　这时，A能看见B，C两人头上的数分别是2，3。A会发现自己头上只可能为3+2=5，或者3-2=1。可到底是l还是5，A无法判断，所以只能回答“不能”。

　　2.再问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。到底是l还是5，A无法判断，只能回答“不能”。这与A实际的回答相同，并不矛盾，所以B无法排除这种情况。

　　如果自己头上是4。则A能看见B，C两人头上的数分别是4，3，A会发现自己头上只可能为4+3=7，或者4-3=１。到底是l还是7，A无法判断，只能回答“不能”。这也与A实际的回答相同，并不矛盾，所以B也无法排除这种情况。

　　B无法判断，只能回答“不能”。

　　3．再问C

　　C会发现自己头上只可能为2+1=3，或者2-1=l。可到底是l还是3．C只能从A或B的回答中入手分析：(以下为C脑中的分析)

　　如果自己头上是1。

　　A会发现自己头上只可能为2+l=3，或者2-1=1。可到底是l还是3，是无法判断的，只能回答“不能”。这与A实际的回答相同，并不矛盾。

　　B会发现自己头上只可能为1+1=2(因为B头上是大于0的整数，所以B头上不能是1-l=0)。B应回答“能”。但这与B实际的回答矛盾。C能以此排除头上是1这种情况。

　　继续分析C头上是3这种情况，会发现毫无矛盾(与实际情况相符)。

　　C将准确判断头上的数是3，所以回答“能”。所以在第三次提问时有人猜出头上的数。

　　我们从每个人的角度出发，分析了头上数是l，2和3的情况。这种方法也是我们解决简单的逻辑推理问题所采用的普遍做法。但如果将问题的规模变大，会发现问题的复杂程度会急剧上升，几乎是多一次推理，问题的复杂度就要变大一倍。

　　靠如此烦琐的推理是不能很好解决问题的。原因在于有大量的“思维嵌套”。即：在C的脑海中要考虑B是如何思考A的想法。此外，这种方法不能够推导出有普遍意义的结论。让我们换一种思路来解决问题。

　　下面我们用第一位、第二位、第三位学生分别表示A，B，C三人。

　　经推论，无论三个数如何变化，无论从谁开始提问，必然是头上数最大的人最先猜出自己头上的数。

　　由上述结论，对于，(a1,a2,a3,k)可以定义f(a1,a2,a3,k)的递推式：

　　当k=1时

　　当a2=a3时，f(a1,a2,a3,1)=1

　　当a2＞a3时，f(a1,a2,a3,1)=f(a2-a3,a2,a3,2)+2

　　当a2＜a3时，f(a1,a2,a3,1)=f(a3-a2,a2,a3,3)+1

　　当k=2时

　　当a1=a3时，f(a1,a2,a3,2)=2

　　当a2＞a3时，f(a1,a2,a3,2)=f(a1,a1-a3,a3,1)+1

　　当a2＜a3时，f(a1,a2,a3,2)=f(a1,a3-a1,a3,3)+2

　　当k=3时

　　当a1=a2时，f(a1，a2，a3，3)=3

　　当a1＞a2时，f(al，a2，a3，3)=f(a1，a2，a1-a2,1)+2

　　当al＜a2时，f(a1，a2，a3，3)=f(a1，a2，a2-a1,2)+1

　　由于我们只考虑(a1，a2，a3，k)∈= S3，因此k可由a1,a2,a3三个数直接确定，因此f(a1,a2,a3,k)可以简化为f(a1,a2,a3)。

　　利用上面的公式，通过计算机编程来辅助解决问题。

　　由于建立了线性的递推关系，因此避免了问题规模随着提问次数呈指数型增长，有效地解决了问题，其解决方法是建立在对问题的深入分析之上的。现在让我们总结解决问题中思路的主线：

[1] [2]  下一页