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

猜数问题的研究

猜数问题的研究

上海市复旦附中 高二(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页

猜数问题的研究

1. 当a1?a3时，f?a1,a2,a3,2??2

2. 当a1?a3时，f?a1,a2,a3,2??f?a1,a1?a3,a3,1??1 3. 当a1?a3时，f?a1,a2,a3,2??f(a1,a3?a1,a3,3)?2 3) 当k=3时

1. 当a1?a2时，f?a1,a2,a3,3??3

2. 当a1?a2时，f?a1,a2,a3,3??f?a1,a2,a1?a2,1??2 3. 当a1?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。

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

提炼重要的前提条件→考虑何种情形为“终结情形”→对非“终结情形”建立推理的等价关系→考虑何种情形能归结到“终结情形”→分情况讨论并加以证明→得出结论并改写等价关系→得出公式

整个过程是从分析问题的本质入手，而非一味单纯地从每个人思想出发，并推导出普遍意义的结论。从综观全局的角度分析问题，避免了最烦琐的“思维嵌套”，并且使得问题规模从指数型转变为线性。

二、第一种推广

问题描述：

一位逻辑学教授有n(n?3)名非常善于推理且精于心算的学生。有一天,教授给他们n人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个大于0的整数，且某个数等于其余n-1个数的和。于是，每个学生都能看见贴在另外n-1个同学头上的整数，但却看不见自己的数。

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

我们的问题就是：证明是否一定有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数，分析整个推理的过程，并总结出结论。

我们对n=3时的定义加以修改：

第6页 共21页

猜数问题的研究

定义：

定义1： 用n+1元组(a1,a2,?,an,k)，a1,a2,?,an?Z?，k??1,2,?n?来描述推

理过程中的一种情形，其中n个人头上数分别为a1,a2,?,an，从第一位学生开始提问，且当前的被提问者为第k位学生。

性质F1：对于n+1元组(a1,a2,?,an,k)，第k位学生可以不依靠别人的回答进行

推理，能够直接判断出自己头上数，并称n+1元组描述的情形为“终结情形”。

性质F2：对于n+1元组(a1,a2,?,an,k)，ak?max?a1,a2,?,an?，并称n+1元组

描述的情形为“一类情形”。

性质F3：对于n+1元组(a1,a2,?,an,k)，ak?max?a1,a2,?,an?,并称n+1元组

描述的情形为“二类情形”。

定义2：集合S1??(a1,a2,?,an,k)(a1,a2,?,an,k)满足性质F1?。 定义3：集合S2??(a1,a2,?,an,k)(a1,a2,?,an,k)满足性质F2?。 定义4：集合S3??(a1,a2,?,an,k)(a1,a2,?,an,k)满足性质F3?。 定义5：若对于n+1元组(a1,a2,?,an,k)

1) 若第k位学生不能够猜出头上的数，记f?a1,a2,?,an,k????。 2) 若第k位学生能够猜出头上的数，记f?a1,a2,?,an,k?为从第一位学

生开始提问直到猜出头上的数的过程中总共的提问次数。

定义6：对于n+1元组(a1,a2,?,an,k)，记g?a1,a2,?,an,k,R???T,F?（表示真

或假），R?Z?，表示当三位学生头上的数分别为a1,a2,?,an，第k位学生是否在恰在第R次提问时最先猜出头上的数为ak。

定义7：对于n+1元组(a1,a2,?,an,k)，记h?a1,a2,?,an,k,R???T,F?（表示真

或假），R?Z?，表示当三位学生头上的数分别为a1,a2,?,an，第k位学生是否能够在第R次提问时排除头上的数为ak的情况。 定义8：对于(a1,a2,?,an,k),记M??ai?i?1k?1i?k?1?aniW?max?a1,?,ak?1,ak?1,?,an?。，

u?1i?1n对于

(a1,a2,?,an,k)，

?u??1,2,?,n?,au??ai?i?u?1?ai，

?v??1,2,?n?\\?k?,av?W。au?max?a1,a2,?,an??max?av,ak?。所以对第k位

学生而言，头上的数可能有两种情况：?ai?i?1k?1i?k?1?ani?M（当au?ak时）或

av?(?ai?i?1k?1i?k?1?ani?av)?W?(M?W)?2W?M（当au?av时）。

第7页 共21页

猜数问题的研究

考虑(a1,a2,?,an,k)?S1。由于?ai?i?1k?1i?k?1?ani?M?0，不能直接排除。而当

且仅当av?(?ai?i?1k?1i?k?1?ani?av)?W?(M?W)?2W?M?0时，能够直接排除这

种情况。即?(a1,a2,?,an,k)?S1?2W?M?0。

对于(a1,a2,?,an,k)?S1，即2W?M?0。若有av?W，av??W，其中v,v???1,2,?n?\\?k?,v?v?，则必然有2W?av?av??M，矛盾。所以除第k位学生外剩下学生中仅有第v位学生头上的数av?W。

当第k位学生假设自己头上是某数，并通过推理发现别人理应能够在前n-1次提问中最先猜出头上的数，就可以根据实际上别人并没有猜出这一矛盾来排除其中一种情况。

1) 当k?u时，即ak?M，因此第k位学生需排除头上数是2W?M。令

??2W?M ?i??1,2,?,n?\\?k?,ai??ai，ak2) 当k?u时，即ak?2W?M，因此第k位学生需排除头上数是M。令

??M ?i??1,2,?,n?\\?k?,ai??ai，ak与n=3时的问题原形类似，可以得到如下式子：

g?a1,a2,?,an,k,R??T

?,a2?,?,an?,k,R??T ?h?a1?,a2?,?,an?,1,R?(k?1)??g?a1?,a2?,?,an?,2,R?(k?2)??? ?g?a1?,a2?,?,an?,n?1,R?(k?1)??g?a1?,a2?,?,an?,n,R?k??T ?g?a1?,a2?,?,an?,k,R? 注：上面总共n-1项，其中不含g?a1?,a2?,?,an?,k?1,R?1??g?a1?,a2?,?,an?,k?1,R?(n?1)????g?a1

分别考虑(a1,a2,?,an,k)?S2和(a1,a2,?,an,k)?S3两种情形：

1) 当(a1,a2,?,an,k)?S2，有ak?max?a1,a2,?,an?，则ak?2W?M。由

??M的情况。 于S1?S2??，第k位学生须通过推理排除头上数为akV?min?f(a1,a2,?,an,k)(a1,a2,?,an,k)?S2,g(a1,a2,?,an,k,f(a1,a2,?,an,k))?T?若?(a1,a2,?,an,k)?S2满足g(A1,A2,?,An,k,f(A1,A2,?,An,k))?T，记

?(a1,a2,?,an,k)?S2。满足

f?a1,a2,?,an,k??V，

?,a2?,?,an?,i,Vi??T。g?a1,a2,?,an,k,V??T，?i??1,2,?,n?\\?k?，g?a1?,a2?,?,an?,i??Vi，而Vi?V，矛盾。 因此f?a1结论：对?(a1,a2,?,an,k)?S2，g?a1,a2,?,an,k,R??F,R?Z?。

第8页 共21页

猜数问题的研究

2) 当

(a1,a2,?,an,k)?S3，且

(a1,a2,?,an,k)?S1。有

ak?m?a1,a2x,?,an?，ak?M，第k位学生须通过推理排除头上数为

??2W?M的情况。此时有av??max?a1?,a2?,?,an??,因此ak?,?,an?,v,Vv??S3。 ?a1?,a2?,a2?,?,an?,k,V??T 由前面结论1)推得g(a1,a2,?,an,k,V)?T?h?a1由于?(a1,a2,?,an,k)?S2，g?a1,a2,?,an,k,R??F,R?Z?。当i?v?,a2?,?,an?,i)?S2，由上述结论得g?a1?,a2?,?,an?,i,Vi??F。因此时,有(a1?,a2?,?,an?,v,Vv??T。 g(a1,a2,?,an,k,V)?T?g?a1我们可以从考虑(a1,a2,?,an,k)?S3，变为考虑

?,?,an?,v,Vv??S3。这样就形成了一个线性的推理方式，而非先前?a1?,a2分支庞大的推理方式。

由于可以只考虑(a1,a2,?,an,k)?S3，若(a1,a2,?,an,k)?S1，可以转而考虑

?,?,an?,v,Vv??S3，ak??a1?,a2?2W?M?M?ak。由于n个数不可能无穷的递减，

因此在有限次转化后必然达到“终结情形”。

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

由上述结论，对于(a1,a2,?,an,k)，可以定义f?a1,a2,?,an,k?的递推式： 1) 当2W?M?0时，f?a1,a2,?,an,k??k

2) 当2W?M?0时

??2W?M 设ai??ai，其中i?k，ak?,a2?,?,an?,v??k?v a) 当vk时，f?a1,a2,?,an,k??f?a1由于我们只考虑(a1,a2,?,an,k)?S3，因此k可由n个数直接确定，因此

f?a1,a2,?,an,k?可以简化为f?a1,a2,?,an?。

利用上面的公式，通过计算机编程来解决问题。参见源程序2。

至此，第一种推广情形就解决了。可以发现n=3时情形的证明，对解决一般情形提供了很好的对比，使得我们能够较为轻松地解决问题，这其实也是建立在对n=3时的情形的分析之上的。

三、第二种推广

问题描述：

一位逻辑学教授有n(n?3)名非常善于推理且精于心算的学生。有一天,教授给他们n人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个

第9页 共21页

猜数问题的研究

人的纸条上都写了一个大于0的整数，并将他们分成了两组（一组学生有m人，且m?n/2，且学生并不知道如何分组），且两组学生头上数的和相等。于是，每个学生都能看见贴在另外n-1个同学头上的整数，但却看不见自己的数。

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

我们的问题就是：证明是否一定有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数，分析整个推理的过程，并总结出结论。

由于当n=3时，m只可能为2，即为问题原形，而对于m=n-1，即第一种推广情形。因此在下文只讨论n>3，m

对于每个人判断自己头上的数，依据分组情况不同，头上的数就可能不同。 对(A1,A2,?,An,k)，第k位学生可以看见除自己外所有学生头上的数，并假设在某种分组情况下，可以计算出与自己不同组的学生头上数的和，由题目条件

m“两组学生头上数的和相等”，可以计算出自己头上的数。由于有Cn种分组情况，

m因此相对应头上的数有Cn种（其中可能也包括了一部分重复的数及非正整数）。

定义：

定义1： 用n+1元组(A1,A2,?,An,k)，A1,A2,?,An?Z?，k??1,2,?n?来描述

推理过程中的一种情形，其中n个人头上数分别为A1,A2,?,An，从第一位学生开始提问，且当前的被提问者为第k位学生。

性质F1：对于n+1元组(A1,A2,?,An,k)，第k位学生可以不依靠别人的回答进

行推理，能够直接判断出自己头上数，并称n+1元组描述的情形为“终结情形”。

性质F2：对于n+1元组(A1,A2,?,An,k)，Ak?max?A1,A2,?,An?，并称n+1元

组描述的情形为“一类情形”。

性质F3：对于n+1元组(A1,A2,?,An,k)，Ak?max?A1,A2,?,An?,并称n+1元组

描述的情形为“二类情形”。

定义2：集合S1??(A1,A2,?,An,k)(A1,A2,?,An,k)满足性质F1?。 定义3：集合S2??(A1,A2,?,An,k)(A1,A2,?,An,k)满足性质F2?。 定义4：集合S3??(A1,A2,?,An,k)(A1,A2,?,An,k)满足性质F3?。 定义5：若对于n+1元组(A1,A2,?,An,k)

1) 若第k位学生不能够猜出头上的数，记f?A1,A2,?,An,k????。 2) 若第k位学生能够猜出头上的数，记f?A1,A2,?,An,k?为从第一位学

生开始提问直到猜出头上的数的过程中总共的提问次数。

第10页 共21页

猜数问题的研究

定义6：对于n+1元组(A1,A2,?,An,k)，记g?A1,A2,?,An,k,R???T,F?（表示真

或假），R?Z?,表示当三位学生头上的数分别为A1,A2,?,An，第k位学生是否在恰在第R次提问时最先猜出头上的数为ak。

定义7：对于n+1元组(A1,A2,?,An,k)，记h?A1,A2,?,An,k,R???T,F?（表示真或假），R?Z?,表示当三位学生头上的数分别为A1,A2,?,An，第k位学生是否能够在第R次提问时排除头上的数为ak的情况。 定义8：对于(A1,A2,?,An,k),记M??ai?i?1k?1i?k?1?aniW?max?A1,?,Ak?1,Ak?1,?,An?。，

定义9：对于(A1,A2,?,An,k)，用X指代第k位学生推测的任意一种分组情况。

定义G(X)为第k位学生假设分组X情况下两组学生头上数的和。

?定义10：对于(A1,A2,?,An,k)，当第k学生在考虑某一可能分组的情况下，记Ak为所推测出的头上数的可能值。

定义11：对于(A1,A2,?,An,k)，定义At1?At2???Atn?1，其中

?t1,t2,?,tn?1??{1,2,?n}\\?k?。

定义12：对于(A1,A2,?,An,k)，定义分组T：选取第t1,t2,?,tm位学生为一组，

剩下的学生为另一组（第k位学生在这一组）。则G(T)??Ati

i?1m对于(A1,A2,?,An,k)，考虑分组T的情况，G(T)??Ati?i?1mi?m?1?Atn?1i? ，显?Ak???Ati?然Aki?1mi?m?1?Atn?1i?At1（第一个求和符号有m项，第二个求和符号有n-1-m

项，由于m?n/2?n?m?n?1?m，且At1?At2???Atn?1）。

对于(A1,A2,?,An,k)任意一个分组X，设?x1,x2,?,xn?1??{1,2,?n}\\?k? 1) 当与第k位学生不同组的学生有m人时，设G(X)??Axi（m项）。

i?1m显然有G(T)??Ati??Axi?G(X)

i?1i?1mmm???Axi?Aki?1mi?m?1?Axn?1i?2?Axi??Axi?i?1i?1mi?m?1?Axn?1i?2?Axi??Axi?2G(X)?M

i?1i?1mn?12) 当与第k位学生同组的学生有m人时，设G(X)??Axi（n-m项）。

i?1n?m第11页 共21页

猜数问题的研究

显然有G(T)??Ati??Ati??Axi?G(X)

i?1i?1i?1mn?mn?m???Axi?Aki?1n?mi?n?m?1?Axn?1i?2?Axi??Axi?i?1i?1n?mn?mi?n?m?1?Axn?1i?2?Axi??Axi?2G(X)?M

i?1i?1n?mn?1考虑(A1,A2,?,An,k)?S1的条件：

I. 当(A1,A2,?,An,k)?S2。

?，这种情况考虑在分组T的情况下，Ak?max?A1,A2,?,An??At1?Ak不同于实际情况，需要进行推理。得到结论：?(A1,A2,?,An,k)?S2，(A1,A2,?,An,k)?S1。 II. 当(A1,A2,?,An,k)?S3。

考虑实际分组B的情况

1) 当与第k位学生不同一组的学生有m人时，G(B)??Abi?i?1mn?1i?m?1?Abii?Ak。

???Ati?在分组T的情况下，有Aki?1mi?m?1?At??Ab??Abiii?1i?m?1n?mi?1n?1mn?1?Ak。

2) 当与第k位学生同一组的学生有m人时，G(B)??Abi?当m?n/2时，即为上面一种情况，因此只考虑m?n/2

???Ati?在分组T的情况下，有Aki?1mi?n?m?1?Abn?1i?Ak。

i?m?1?At??Abii?1n?1n?mi?i?n?m?1?Abn?1i?Ak。

?。因此实际分组B要使得(A1,A2,?,An,k)?S1，必然要满足Ak?Ak只可能是上面第一种情况，且满足?Abi?i?1mi?m?1?Ab??Atii?1mn?1mi?i?m?1?Atmn?1i，显

然?Ai??Abi?i?1i?1n?1mi?m?1?Ab??Atii?1n?1mi?i?m?1?Atn?1i，因此可得?Abi??Ati，

i?1i?1即G(B)?G(T)。

显然G(X)?G(T)?G(B)，在此条件下，若存在可能的分组C满足

??2G(C)?M?2G(B)?M?Ak。显然由于G(C)?G(B)，Ak??0，即2G(C)?M?0。 (A1,A2,?,An,k)?S1，必然有Ak若不存在可能的分组C满足G(C)?G(B)，即任意分组G(X)?G(B),则At1?At2???Atn?1。

第12页 共21页

猜数问题的研究

进一步分析对可能的分组C满足G(C)?G(B)，何时满足2G(C)?M?0。分两种情况考虑：

1) 当At2,At3,?,Atn?1不全相等时，必然有At2?Atn?1，考虑如下分组C：

第t1,t3,t4?,tm?1,tm,tn?1位学生为一组，第k,t2,tm?1,tm?2,?,tn?2位学生为一组，此时显然有G(C)?At1??Ati?Atn?1??Ati?G(B)。

i?3i?1mm需满足2G(C)?M?0，即G(C)?M?G(C)，因此

At1??Ati?Atn?1?G(C)?M?G(C)?At2?i?3mi?m?1?Atn?2i。另一方面，

At1?At2,At3?Atm?1,At4?Atm?2,?,Atn?m?Atn?2，而m?n?m，因

此At1??Ati?Atn?1?At1??Ati?At1??Ati?At2?i?3i?3i?3mmn?mi?m?1?Atn?2i，矛

盾。因此，?(A1,A2,?,An,k)满足At2?Atn?1,(A1,A2,?,An,k)?S1。 2) 当At2,At3,?,Atn?1全相等时，不妨设，At1?p，

?i??2,3,?,n?1?,Ati?q。

考虑分组C：m个头上数为q的学生为一组，剩下的学生为一组（第k位学生在这组中）。

由于2G(C)?M?0，即2mq?[p?(n?2)q]?0，因此(2m?n?2)q?p。

1. 当m?n/2时，再来考虑分组D：头上数是p的学生与n-m-1个

头上数是q的学生在一组, 剩下学生为一组。由于m?n/2，因此G(D)?G(B)。

由于2G(D)?M?0，因此2[p?(n?m?1)q]?a?(n?2)b，因此p?(2m?n)q，观察得到的两个不等式，显然矛盾，因此当

m?n/2时，?(A1,A2,?,An,k)满足At1?Atn-1,(A1,A2,?,An,k)?S1。2. 当m?n/2时，可以得到Ak??Ati?i?1mi?m?1?Atn?1i ?At1?p，且2q?p。

因此，(A1,A2,?,An,k)?S1的条件为：

1. (A1,A2,?,An,k)?S3 2. At1?At2???Atn?1或

m?n/2,p,q?Z?,2q?p,Ak?At1?p,?i??2,3,?,n?1?,Ati?q

第13页 共21页

猜数问题的研究

分情况进行讨论(A1,A2,?,An,k)?S1的情况： I. 对于(A1,A2,?,An,k)?S2

若?(A1,A2,?,An,k)?S2，g(A1,A2,?,An,k,f(A1,A2,?,An,k))?T，记V?min?f(A1,A2,?,An,k)(A1,A2,?,An,k)?S2,g(A1,A2,?,An,k,f(A1,A2,?,An,k))?T??(A1,A2,?,An,k)?S2。

g?A1,A2,?,An,k,V??T。

满足

f?A1,A2,?,An,k??V，

若第k位学生能够猜出自己头上的数，则他一定要通过推理排除头上数所有可能情况中与实际不相等的值。

A1,A2,?An?,因此由于(A1,A2,?,An,k)?S2，即Ak?ma?xma?Ax1,A2,?An??ma?Atx1,At2,?,Atn?1?。考虑分组T的情况,

?，因此需要排Ak?max?A1,A2,?,An??max?At1,At2,?,Atn?1??At1?Ak除这种情况。令Ai??Ai,i??t1,t2,?,tn?1?。

g?A1,A2,?,An,k,R??T

?,A2?,?,An?,k,R??T ?h?A1?,A2?,?,An?,t1,Rt1??g?A1?,A2?,?,An?,t2,Rt2??? ?g?A1?,A2?,?,An?,tn?1,Rtn?1??T ?g?A1注：上面Rt1,Rt2,?,Rtn?1?Z?为代定变量，显然有

Rt1,Rt2,?,Rtn?1?R，由于具体值与结论无关，因此不必讨论。 ??At1 1) 当Ak?,A2?,?,An?,t)?S2,t??t1,t2,?,tn?1?。?i??则可得(A11,2,?,n?1?，

?,A2?,?,An?,ti,Vti??T，f?A1?,A2?,?,An?,ti??Vti，而Vti?V，使得g?A1矛盾。

因此得到结论：对于?(A1,A2,?,An,k)?S2，若在分组T的情

??At1，则g?A1,A2,?,An,k,R??F,R?Z?。 况下满足Ak??At1 2) 当Ak???Ati?由于，因此等号成立的条件为Aki?1mi?m?1?Atn?1i?At1，由于

At1?At2???Atn?1，因此仅当m?n/2存在这种情况，此时At2?At3??Atn?1。

1. 若At1?At2

考虑实际分组B的情况，显然Ab1?Ab2??Abn?1，

Ak??Abi?i?1mi?m?1?Abn?1i?Ab1，此时(A1,A2,?,An,k)?S2。

2. 若At1?At2

?,A2?,?,An?,t1??S3显然?A1第14页 共21页

，对?i??2,3,?,n?，

猜数问题的研究

?,?,An?,ti??S2。 ?A1?,A2?,A2?,?,An?,ti,Vti??T若?i??2,?,n?1?，g?A1，

?,a2?,?,an?,ti??Vti，而Vti?V，矛盾。 f?a1?,A2?,?,An?,t1,Vt1??T。 因此g?A1,A2,?,An,k,V??T?g?A1设At1?p，?i??2,3,?,n?1?,Ati?q。

由于m?n/2，对第k位学生只有两种本质不同的分组情况，即第k位学生与第t1位学生在同一组或不在同一组，两种情况对应头上数的可能值分别是：

???Ati?Ak??Ati??Ati?2q?p及Aki?mi?1i?1n?1m?1mi?m?1?Atn?1i?p

?,A2?,?,An?,t1?，第t1位1,2,?,n?1?,A?ti?Ati，对?A1设?i??学生只有两种本质不同的分组情况，两种情况对应头上数的可能值分别是：

A?t1?p及A??t1?2q?p

设?i??1,2,?,n?\\?t1?， Ai???Ai? 。

?,A2?,?,An?,t1,R??T g?A1??,A2??,?,An??,t1,R??T ?h?A1??,A2??,?,An??,k??S3，对?i??2,3,?,n?，显然?A1??,?,An??,ti??S2。 ?A1??,A2??,A2??,?,An??,ti,V?ti??T，若?i??2,?,n?1?，g?A1??,A2??,?,An??,ti??V?ti，而V?ti?V，矛盾。 f?A1?,A2?,?,An?,t1,Vt1??T?g?A1??,A2??,?,An??,k,V?k??T 因此g?A1??,A2??,?,An??,k,Rk??g?A1??,A2??,?,An??,t2,Rt2??? ?g?A1??,A2??,?,An??,tn?1,Rtn?1??T ?g?A1考虑

??,?,An??,k??A1??,A2，

A??t1?2q?p，

?i??2,3,?,n?1?,A??ti?q，对第k位学生只有两种本质不同的

分组情况，两种情况对应头上数的可能值分别是：

???p及Ak????2q?p Ak1,2,?,n?\\?k?，且i?k，Ai????Ai?? 。 设?i????,A2??,?,An??,k,V?k??T g?A1??????,?,An???,t2,V??t2??g?A1??????,?,An???,t2,V??t3??? ?g?A1,A2,A2第15页 共21页

猜数问题的研究

??????,?,An???,tn?1,V??tn?1??T ?g?A1,A2 定义：

???,?,An???,t2?,f?A1???,A2???,?,An???,t2?,?,f?A1???,A2???,?,An???,tn?1??Vmin?min?f?A1???,A2??,A2??,?,An??,k??Vmin 显然f?A1当只有两种本质不同的分组情况时，排除其一即可猜出头上的数，利用上述结论讨论f?A1,A2,?,An,k?。

a) 当k?t1

f?A1,A2,?,An,k?

?,A2?,?,An?,t1??k?t1 ?f?A1??,A2??,?,An??,k??(n?k?t1)?(k?t1) ?f?A1?Vmin?n

b) 当k?t1

f?A1,A2,?,An,k?

?,A2?,?,An?,t1??n?k?t1 ?f?A1??,A2??,?,An??,k??(t1?k)?(n?k?t1) ?f?A1?Vmin?n

由于f?A1,A2,?,An,k??V，?A1,A2,?,An,t1??S3，

?i??2,3,?,n?，?A1,A2,?,An,ti??S2，因此对(A1,A2,?,An,k)，

只有第k位学生和第t1位学生两人可能最先猜出头上的数。

对第t1位学生也只有两种本质不同的分组情况，即第k位学生与第t1位学生在同一组或不在同一组，两种情况对应头上数的可能值分别是：

At1?p及A????t1?2q?p

?Ai 。 1,2,?,n?\\?k?，Ai????设?i???Ai??? 1,2,?,n?，Ai????比较后可发现?i????????,?,A???,t1,Vt1??T ?nh?A1,A2??????,?,An???,t2,V??t2??g?A1??????,?,An???,t2,V??t3??? ?g?A1,A2,A2??????,?,An???,tn?1,V??tn?1??T ?g?A1,A2第16页 共21页

猜数问题的研究

由于对第t1位学生只有两种本质不同的分组情况，因此排除其一即可猜出头上的数，即f?A1,A2,?,An,t1??Vt1。

因而f?A1,A2,?,An,t1??Vt1?Vmin?n 显然f?A1,A2,?,An,t1??f?A1,A2,?,An,k?

则说明第t1位学生将在第k位学生之前猜出头上的数，说明

g?A1,A2,?,An,k,V??F，矛盾。

得到结论：对于?(A1,A2,?,An,k)?S2，若在分组T的情况

??At1，则g?A1,A2,?,An,k,R??F,R?Z?。 下满足Ak

因此综合考虑上述所有情况，得到结论：对于?(A1,A2,?,An,k)?S2，

g?A1,A2,?,An,k,R??F,R?Z?。

II. 对于(A1,A2,?,An,k)?S3

并非所有(A1,A2,?,An,k)?S3，第k位学生都能猜出头上的数，下

面举一个例子：

当n?6,m?3时，考虑(1,1,2,3,3,4,6)?S3（实际分组为1，3，3为一组，1，2，4为一组），对于第6位学生须排除头上数是6的可能（分组为2，3，3为一组，1，1，6为一组），记V?f?1,1,2,3,3,4,6?，g?1,1,2,3,3,4,6,V??T?h?1,1,2,3,3,6,6,V???T，由前面结论可得h?1,1,2,3,3,6,6,V??T?g?1,1,2,3,3,6,1,V1??g?1,1,2,3,3,6,2,V2????g?1,1,2,3,3,6,5,V5?，而?i??1,2,?,5?，(1,1,2,3,3,6,i)?S2，即g(1,1,2,3,3,6,i,Vi)?F。因此

g(1,1,2,3,3,4,6,V)?F，即第6位学生不能最先猜出头上的数。而

?i??1,2,?,5?，(1,1,2,3,3,4,i)?S2，考虑到前面讨论Ⅰ，因此没有人能猜

出头上的数。

由于对于能够猜出头上数的情形，在形式上不具特殊性，因此我们只有在推理过程中不断判定是否有可能猜出头上的数。

对于(A1,A2,?,An,k)，若Ak??Ati?i?1mi?m?1?Atn?1i，则分组T的情况下，

???Ati?Aki?1mi?m?1?Atn?1i1,2,?,n?1?,A?ti?Ati，?Ak?max?1,2,?,n?，?i???,A2?,?,An?,ti)?S2，由前面讨论Ⅰ可得1,2,?,n?1?，(A1则?i??第17页 共21页

猜数问题的研究

g(A1,A2,?,An,k,V)?F。显然有Ak??Ati?i?1mi?m?1?Atn?1i，因此判定条件之

一为Ak??Ati?i?1mi?m?1?Atn?1i。

可能有多个学生头上的数同为最大数，若有多个学生头上的数同为最大数，则At1?Ak。下面分情况讨论： 1. 当At2?Atn?1或m?n/2

???Ati?则分组T的情况下，Aki?1mi?m?1?Atn?1i?At1?Ak，由前面的

判定条件，在这种情形下，第k位学生不能够最先猜出头上的数。

当Ati?Ak，利用前面结论可知第ti位学生不能够最先猜出头上的数。而当Ati?Ak，(A1,A2,?,An,ti)?S2。因此没有人能猜出头上的数。

2. 当At2?At1?Ak，m?n/2

a) 若At2?Atn?1，此时即为第1)种情况。

b) 若At2?At3???Atn?1，则所有n个数都相等，此时

(A1,A2,?,An,k)?S1。 3. 当At1?At2，m?n/2，n?5

显然当n为奇数时，必然有m?n/2，即第1)种情况。因此下面只考虑n为偶数。

a) 若At2?Atn?1，此时即为第1)种情况。 b) 若At2?At3???Atn?1

对第k位学生只有两种本质不同的分组，不妨设Ak?At1?p，?i??2,3,?,n?1?,Ati?q。 i. 若2q?p，(A1,A2,?,An,k)?S1。

??2q?p，令ii. 若2q?p，考虑须排除的情况，Ak?i??1,2,?,n?1?,A?ti?Ati。

?,A2?,?,An?,ti)?S2 显然?i??2,3,?,n?1?，(A1?,A2?,?,An?,t1,Vt1??T g?A1,A2,?,An,k,V??T?g?A1?,A2?,?,An?,t1?，则A??t1?2q?p，令考虑?A1?i??2,3,?,n?1?,A??ti?A?ti。

?,?,An?,k)?S2，?i??2,3,?,n?1?,A??ti?Ati?q。显然(A1?,A2??,A2??,?,An??，可以发现即为第1)种情况。因此，第k观察A1位学生不能够最先猜出头上的数。

当Ati?Ak，利用前面结论可知第ti位学生不能够最先

第18页 共21页

猜数问题的研究

猜出头上的数。而当Ati?Ak，(A1,A2,?,An,ti)?S2。因此

没有人能猜出头上的数。

4. 当At1?At2，且n?4

则必然有m?2，显然可以得到At2?At3，不妨设Ak?At1?p，At2?At3?q，并称这种两两相等的情形为“A类情形”。

对第k位学生只有两种本质不同的分组方式，考虑须排除的情??2q?p,A?t1?p,A?t2?A?t3?q。 况，Ak?,A2?,?,An?,ti)?S2 显然?i??2,3?，(A1?,A2?,?,An?,t1,Vt1??T g?A1,A2,?,An,k,V??T?g?A1对第t1位学生只有两种本质不同的分组方式，考虑须排除的情

???2q?p,A??t2?A??t3?q。况，A??t1?2q?p,Ak又回到了“A类情形”

又由于四数中始终有一个数在减小，因此有限次推理之后，必然

达到“终结情形”，此时满足条件为2q?p。

因此一定有人能够猜出头上的数。但具体由第k位学生和第t1位学生中哪一人最先猜出头上的数需要具体计算后才能确定。 至此，讨论完所有存在两个以上的学生头上为最大数的情形。

可能的分组C满足G(C)?G(B)，进行讨论。

??2G(C)?M?2G(B)?M?Ak。令在这种情况下，Ak?i??1,2,?,n?1?,A?ti?Ati。 ??At1时 1) 当Ak?,A2?,?,An?,ti)?S2，由前面讨论Ⅰ可得?i??1,2,?,n?1?，(A1g(A1,A2,?,An,k,V)?F。因此第k位学生不能够最先猜出头上的数。

??Ak，因此?i??由At1?Ak1,2,?,n?1?，(A1,A2,?,An,ti)?S2。因

此没有人能够猜出头上的数。 ??At1时 2) 当Ak??max?A1?,A2?,?,An??，可以利用前面对多个学生头此时A?t1?Ak上数同为最大数时的讨论的结果：

1. 当m?n/2（讨论多个最大数时的讨论1）

?,A2?,?,An?,i?，第i位学生不能够1,2,?,n?，考虑?A1对?i??最先猜出头上的数。即没人能猜出头上的数。因此，对于

(A1,A2,?,An,k)，第k位学生不能够最先猜出头上的数。

?，m?n/2（讨论多个最大数时的讨论2） 2. 当A?t2?A?t1?Aka) 当A?t2?A?tn?1

?,A2?,?,An?,i?，第i位学生不1,2,?,n?，考虑?A1对?i??能够最先猜出头上的数。即没人能猜出头上的数。因此，对于(A1,A2,?,An,k)，第k位学生不能够最先猜出头上的数。

第19页 共21页

猜数问题的研究

b) 当A?t2?A?tn?1

??A?t1?A?t2???A?tn?1，因此可以得知由于AkAk?At1?At2???Atn?1，即(A1,A2,?,An,k)?S1。

3. 当A?t2?A?t1，n?5，m?n/2（讨论多个最大数时的讨论3）

a) 当A?t2?A?tn?1

?,A2?,?,An?,i?，第i位学生不对?i??1,2,?,n?，考虑?A1能够最先猜出头上的数，即没人能猜出头上的数。因此，对

于(A1,A2,?,An,k)，第k位学生不能够最先猜出头上的数。 b) 当A?t2?A?tn?1

??A?t1?p，?i??2,3,?,n?1?,A?ti?q。 不妨设Aki. 当2q?p

?,A2?,?,An?,k??S1，于是第k可以由之前讨论得到?A1位学生头上的数仅有一种可能情况，不属于讨论的范围。

ii. 当2q?p

?,A2?,?,An?,i?，第i位学生对?i??1,2,?,n?，考虑?A1不能够最先猜出头上的数，即没人能猜出头上的数。因

此，对于(A1,A2,?,An,k)，第k位学生不能够最先猜出头上的数。

4. 当A?t2?A?t1，且n?4（讨论多个最大数时的讨论4）

显然可以得到A?t2?A?t3，此时不存在实际划分B，使得

G(C)?G(B)，即这种情况不属于讨论的范围。 ??At1时 3) 当Ak?,?,An?,t1??S3，因此，第k位可能最先猜出头上的数，因?A1?,A2此需要继续推理。

结论：对于(A1,A2,?,An,k)?S3，第k位学生可能最先猜出头上的数，需要继续推理的判定条件为：Ak??Ati?i?1mi?m?1?Atn?1i?2G(T)?M，即

??At1。 G(B)?G(T),且对任意可能分组C符合G(C)?G(B)，满足Ak当n?4,m?2，考虑(A1,A2,A3,A4,k)?S3

1) 当Ak?At1，由前面讨论多个最大数时的讨论4，及，一定有人能够猜出

头上的数。

2) 当Ak?At1，显然Ak?At1?At2?At3，因此At1?At2?At3?At1，即

??At1?At3?At2?At1，At2?At3。第k位学生头上数其余两种可能值，Ak???At2?At3?At1?At1。由前面结论，需要继续推理。 Ak由于仅有这两种情况，即不存在情况使得没有人能够猜出头上的数。且推理

第20页 共21页

猜数问题的研究

时四个数始终在减小，因此经过有限次推理之后，必然达到“终结情形”。 而对于第一种推广情形，即n?4,m?3，必然有人能猜出自己头上的数。

因此n?4时的一切情况，必然有人能猜出自己头上的数。

由于现在的推理在加强判定的情况下，依然可能出现多种考虑情况。所以推理已不是线性的推理，整个推理过程将成为树状结构。

由于分组情况繁多，而且判定方式也比较复杂，因此这时计算f?A1,A2,?,An,k?的值已经非人力能够解决，但是已经可以编程解决问题了，参见源程序3。

结束语

本文深入地分析了一个逻辑推理问题，从综观全局的角度来考虑问题的本质联系，而非一味单纯地从每个人思想出发，简化了最烦琐的“思维嵌套”，并在此基础上建立了递推关系，因此避免了问题规模随着推理次数急剧增长，有效地解决了问题。并通过对比将问题推广到更为一般的情形，尤其对于第二种推广情形，存在极为烦琐的讨论，但其讨论问题的核心思想是一致的。对解决逻辑推理的问题提供了一种可以借鉴的方法。

参考文献

《CTSC2001分析》

《算法与数据结构》 傅清祥 王晓东 编著

第21页 共21页

猜数问题的研究

时四个数始终在减小，因此经过有限次推理之后，必然达到“终结情形”。 而对于第一种推广情形，即n?4,m?3，必然有人能猜出自己头上的数。

因此n?4时的一切情况，必然有人能猜出自己头上的数。

由于现在的推理在加强判定的情况下，依然可能出现多种考虑情况。所以推理已不是线性的推理，整个推理过程将成为树状结构。

由于分组情况繁多，而且判定方式也比较复杂，因此这时计算f?A1,A2,?,An,k?的值已经非人力能够解决，但是已经可以编程解决问题了，参见源程序3。

结束语

本文深入地分析了一个逻辑推理问题，从综观全局的角度来考虑问题的本质联系，而非一味单纯地从每个人思想出发，简化了最烦琐的“思维嵌套”，并在此基础上建立了递推关系，因此避免了问题规模随着推理次数急剧增长，有效地解决了问题。并通过对比将问题推广到更为一般的情形，尤其对于第二种推广情形，存在极为烦琐的讨论，但其讨论问题的核心思想是一致的。对解决逻辑推理的问题提供了一种可以借鉴的方法。

参考文献

《CTSC2001分析》

《算法与数据结构》 傅清祥 王晓东 编著

第21页 共21页

本文来源：https://www.bwwdw.com/article/xq9o.html