猜数问题的研究
猜数问题的研究
上海市复旦附中 高二(8) 张宁
摘要：
在逻辑推理中有一类比较特殊的问题——“思维嵌套”问题，即在C的脑海中要考虑B是如何思考A的想法。对于这种问题通常非常抽象，考虑情况又十分繁多，思想极其复杂，用一般方法分析效果极差。本文以一个典型的“思维嵌套”问题——猜数问题为出发点，用一种新的方法从问题本质入手分析，很好的解决了问题，并阐述了新思路的优越性。由本质入手分析，避免了表面上的“思维嵌套”，且总结出了许多结论，使得解决问题的效率大幅度上升。在新思路的指引下将原问题向更普遍的情形推广，虽然问题变得更为繁琐复杂，但是由于把握住问题的命脉，有效地解决了问题。
关键字：推理，思维嵌套，终结情形，一类情形，二类情形，分组 正文：
一、问题原形
问题描述：
一位逻辑学教授有三名非常善于推理且精于心算的学生A，B和C。有一天,教授给他们三人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个大于0的整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。
教授轮流向A，B和C发问：是否能够猜出自己头上的数。经过若干次的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。
我们的问题就是：证明是否一定有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数，分析整个推理的过程，并总结出结论。
我们先分析一个简单的例子，观察每个人是如何进行推理的。
第1页 共21页
猜数问题的研究
假设A，B和C三人，头上的数分别是1，2和3。 1) 先问A
这时，A能看见B，C两人头上的数分别是2，3。A会发现自己头上只可能为3+2=5，或者3-2=1。可到底是1还是5，A无法判断，所以只能回答“不能”。 2) 再问B
B会发现自己头上只可能为3+1=4，或者3-1=2。可到底是2还是4，B只能从A的回答中入手分析：（以下为B脑中的分析）
1. 如果自己头上是2。则A能看见B，C两人头上的数分别是2，3，A
会发现自己头上只可能为3+2=5，或者3-2=1。到底是1还是5，A无法判断，只能回答“不能”。这与A实际的回答相同，并不矛盾，所以B无法排除这种情况。
2. 如果自己头上是4。则A能看见B，C两人头上的数分别是4，3，A
会发现自己头上只可能为4+3=7，或者4-3=1。到底是1还是7，A无法判断，只能回答“不能”。这也与A实际的回答相同，并不矛盾，所以B也无法排除这种情况。 B无法判断，只能回答“不能”。 3) 再问C
C会发现自己头上只可能为2+1=3，或者2-1=1。可到底是1还是3，C只能从A或B的回答中入手分析：（以下为C脑中的分析） 1. 如果自己头上是1。
a) A会发现自己头上只可能为2+1=3，或者2-1=1。可到底是1还
是3，是无法判断的，只能回答“不能”。这与A实际的回答相同，并不矛盾。
b) B会发现自己头上只可能为1+1=2（因为B头上是大于0的整数，
所以B头上不能是1-1=0）。B应回答“能”。但这与B实际的回答矛盾。C能以此排除头上是1这种情况。
2. 如果继续分析C头上是3这种情况会发现毫无矛盾（因为与实际情
况相符）。
C将准确判断头上的数是3，所以回答“能”。 所以在第三次提问时有人猜出头上的数。
我们从每个人的角度出发，分析了头上数是1，2和3的情况。这种方法也是我们解决简单的逻辑推理问题所采用的普遍做法。但如果将问题的规模变大，
第2页 共21页
猜数问题的研究
会发现问题的复杂程度会急剧上升，几乎是多一次推理，问题的复杂度就要变大一倍。更复杂的例子，限于篇幅就不举了，但复杂程度是可以想见的。
靠如此烦琐的推理是不能很好解决问题的。原因在于有大量的“思维嵌套”，即：在C的脑海中要考虑B是如何思考A的想法。此外，这种方法不能够推导出有普遍意义的结论。让我们换一种思路来解决问题。
定义：
下面我们用第一位、第二位、第三位学生分别表示A，B，C三人
定义1： 用四元组?a1,a2,a3,k?，a1,a2,a3?Z?，k??1,2,3?来描述推理过程中的
一种情形，其中三个人头上数分别为a1,a2,a3，从第一位学生开始提问，且当前的被提问者为第k位学生。
性质F1：对于四元组?a1,a2,a3,k?，第k位学生可以不依靠别人的回答进行推理，
能够直接判断出自己头上数，并称四元组描述的情形为“终结情形”。
性质F2：对于四元组?a1,a2,a3,k?，ak?max?a1,a2,a3?，并称四元组描述的情形
为“一类情形”。
性质F3：对于四元组?a1,a2,a3,k?，ak?max?a1,a2,a3?,并称四元组描述的情形
为“二类情形”。
定义2：集合S1???a1,a2,a3,k??a1,a2,a3,k?满足性质F1?。 定义3：集合S2???a1,a2,a3,k??a1,a2,a3,k?满足性质F2?。 定义4：集合S3???a1,a2,a3,k??a1,a2,a3,k?满足性质F3?。 定义5：若对于四元组(a1,a2,a3,k)
1) 若第k位学生不能够猜出头上的数，记f?a1,a2,a3,k????。 2) 若第k位学生能够猜出头上的数，记f?a1,a2,a3,k?为从第一位学生
开始提问直到猜出头上的数的过程中总共的提问次数。
定义6：对于四元组(a1,a2,a3,k)，记g?a1,a2,a3,k,R???T,F?（表示真或假），
R?Z?，表示当三位学生头上的数分别为a1,a2,a3，第k位学生是否在恰在第R次提问时最先猜出头上的数为ak。
定义7：对于四元组(a1,a2,a3,k)，记h?a1,a2,a3,k,R???T,F?（表示真或假），
R?Z?，表示当三位学生头上的数分别为a1,a2,a3，第k位学生是否能够在第R次提问时排除头上的数为ak的情况。
找出问题的前提，即已知条件： 1) 某两个数的和等于第三个
2) 每个人的纸条上都写了一个大于0的整数
每个人头上的数不是另两数的和就是另两数的差。由于不能直接判断一定是其中某个数，就只能采取排除法。由于他们不会猜错，因此在下面只需考虑他们第3页 共21页
猜数问题的研究
如何能够排除头上数不同于实际的可能情况。
考虑四元组(a1,a2,a3,k)?S1，设i,j满足?i,j,k???1,2,3?，则第k位学生头上的有两种情况ak?ai?aj或ak?ai?aj。其中ai?aj?0,不能直接排除。由于ai?aj?0，所以当且仅当ai?aj?0能够直接排除这种情况。即
?(a1,a2,a3,k)?S1?ai?aj，其中?i,j,k???1,2,3?。
显然ak?ai?aj，ak?max?a1,a2,a3?，因此S1?S3。注意到集合S2与S3的定义，显然S2?S3??，因此必然有S1?S2??。
考虑四元组(a1,a2,a3,k)?S1，即第k位学生不能直接猜出自己头上的数，就需要通过推理来排除头上数的两种情况中的一种。当第k位学生假设自己头上是某数，并通过推理发现别人理应能够在前两次提问中最先猜出头上的数，就可以根据实际上别人并没有猜出这一矛盾来排除其中一种情况。（可以参考前面例子中对C思想的分析）
显然三位学生都不可能通过推理排除自己头上数的实际情况（因为他们是永远不会猜错的）。所以下面仅需考虑如何排除头上数不同于实际的另一种情况。
对于四元组(a1,a2,a3,k)，为了讨论方便，不妨设a3?a1?a2。 注:下面的?为析取符号，即T?T?T,T?F?T,F?T?T,F?F?F 1) 当k=1时
g?a1,a2,a3,k,R??T
?g?a3?a2,a2,a3,1,R1??T ?h?a2?a3,a2,a3,1,R1??T
?g?a2?a3,a2,a3,2,R1?2??g?a2?a3,a2,a3,3,R1?1??T 2) 当k=2时
g?a1,a2,a3,k,R??T
?g?a1,a3?a1,a3,2,R2??T ?h?a1,a1?a3,a3,2,R2??T
?g?a1,a1?a3,a3,1,R2?1??g?a1,a1?a3,a3,3,R2?2??T 3) 当k=3时
g?a1,a2,a3,k,R??T
?g?a1,a2,a1?a2,3,R3??T ?h?a1,a2,a1?a2,3,R3??T
1,2,3?，ai??ai，a?j?aj。对于四元组(a1,a2,a3,k)，设i,j满足?i,j,k?????ai?aj,当ak?ai?aj时,ak??ai?aj。 当ak?ai?aj时,ak?g?a1,a2,a1?a2,1,R3?2??g?a1,a2,a1?a2,2,R3?1??T
1. 当k?i时，设Vi?V?(k?i),当k?i时，设Vi?V?(n?k?i)。 2. 当k?j时，设Vj?V?(k?j),当k?j时，设Vj?V?(n?k?j)。
第4页 共21页
猜数问题的研究
?,a2?,a3?,i,Vi??g?a1?,a2?,a3?,j,Vj??T 由上面定义可得g(a1,a2,a3,k,V)?T?g?a1
分别考虑四元组(a1,a2,a3,k)?S2和(a1,a2,a3,k)?S3两种情形：
?a1,a2,a3?，则ak?ai?aj。由于1) 当(a1,a2,a3,k)?S2，有ak?max??ai?aj的情况。 S1?S2??，第k位学生须通过推理排除头上数为akV?min?f(a1,a2,a3,k)(a1,a2,a3,k)?S2,g(a1,a2,a3,k,f(a1,a2,a3,k))?T?。?,a2?,a3?,j,Vj??T，因此f?a1?,a2?,a3?,i,Vi??T或g?a1?,a2?,a3?,i??Vi得到g?a1若?(a1,a2,a3,k)?S2满足g(a1,a2,a3,k,f(a1,a2,a3,k))?T，记
?(a1,a2,a3,k)?S2满足f?a1,a2,a3,k??V，g?a1,a2,a3,k,V??T，则可以
?,a2?,a3?,j??Vj。ak??ai?aj?ai??a?j，因此(a1?,a2?,a3?,i)?S2，或f?a1?,a2?,a3?,j)?S2，而Vi?V，Vj?V，矛盾。 (a1结论：对?(a1,a2,a3,k)?S2，g?a1,a2,a3,k,R??F,R?Z?。
xa1,a2,a3?，2) 当(a1,a2,a3,k)?S3，且(a1,a2,a3,k)?S1。有ak?ma???ai?aj的情况。ak?ai?aj，第k位学生须通过推理排除头上数为ak由于(a1,a2,a3,k)?S1，显然ai?aj。
?,a2?,a3?,k,V)?T 由前面讨论1)可推得g?a1,a2,a3,k,V??T?h(a1?,a2?,a3?,i)?S3，(a1?,a2?,a3?,j)?S2。因此a) 当ai?aj,即ai??a?j，(a1?,a2?,a3?,j,Vj??F，g(a1,a2,a3,k,V)?T?g?a1?,a2?,a3?,i,Vi??T。g?a1
?,a2?,a3?,j)?S3，(a1?,a2?,a3?,i)?S2。因此b) 当aj?ai,即a?j?ai?，(a1?,a2?,a3?,i,Vi??F，g(a1,a2,a3,k,V)?T?g?a1?,a2?,a3?,j,Vj??T。g?a1
我们可以从考虑四元组(a1,a2,a3,k)?S3，变为考虑四元组
?,a2?,a3?,i)?S3或(a1?,a2?,a3?,j)?S3。这样就形成了一个线性的推理方(a1式，而非先前分支庞大的推理方式。
由于可以只考虑(a1,a2,a3,k)?S3，若(a1,a2,a3,k)?S1，可以转而考虑四元
?,a2?,a3?,i)?S3或(a1?,a2?,a3?,j)?S3。由于三个数不可能无穷的递减，因此在组(a1有限次转化后必然达到“终结情形”。
结论：无论三个数如何变化，无论从谁开始提问，必然是头上数最大的人最先猜出自己头上的数。
由上述结论，对于(a1,a2,a3,k)，可以定义f?a1,a2,a3,k?的递推式： 1) 当k=1时
1. 当a2?a3时，f?a1,a2,a3,1??1
2. 当a2?a3时，f?a1,a2,a3,1??f?a2?a3,a2,a3,2??2 3. 当a2?a3时，f?a1,a2,a3,1??f?a3?a2,a2,a3,3??1 2) 当k=2时
第5页 共21页