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

(完整版)算法合集之《猜数问题的研究》
猜数问题的研究

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

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

正文：
一、问题原形
问题描述：
一位逻辑学教授有三名非常善于推理且精于心算的学生A,B和C.有一天,教授给他们三人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个大于0的整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数,但却看不见自己的数。
教授轮流向A,B和C发问：是否能够猜出自己头上的数.经过若干次的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来.
我们的问题就是:证明是否一定有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数，分析整个推理的过程，并总结出结论。
我们先分析一个简单的例子，观察每个人是如何进行推理的。
假设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的情况。这种方法也是我们解决简单的逻辑推理问题所采用的普遍做法。但如果将问题的规模变大,会发现问题的复杂程度会急剧上升，几乎是多一次推理，问题的复杂度就要变大一倍。更复杂的例子，限于篇幅就不举了，但复杂程度是可以想见的.
靠如此烦琐的推理是不能很好解决问题的.原因在于有大量的“思维嵌套"，即:在C的脑海中要考虑B是如何思考A的想法。此外，这种方法不能够推导出有普遍意义的结论。让我们换一种思路来解决问题。
定义:
下面我们用第一位、第二位、第三位学生分别表示A，B，C三人
定义1： 用四元组,，来描述推理过程中的一种情形，其中三个人头上数分别为，从第一位学生开始提问，且当前的被提问者为第k位学生。
性质：对于四元组，第k位学生可以不依靠别人的回答进行推理，能够直接判断出自己头上数,并称四元组描述的情形为“终结情形”。
性质：对于四元组，,并称四元组描述的情形为“一类情形"。
性质:对于四元组，,并称四元组描述的情形为“二类情形”。
定义2:集合.
定义3：集合。
定义4:集合。
定义5：若对于四元组
1) 若第k位学生不能够猜出头上的数，记。
2) 若第k位学生能够猜出头上的数,记为从第一位学生开始提问直到猜出头上的数的过程中总共的提问次数.
定义6：对于四元组,记（表示真或假），，表示当三位学生头上的数分别为，第k位学生是否在恰在第R次提问时最先猜出头上的数为。
定义7:对于四元组,记(表示真或假），，表示当三位学生头上的数分别为，第k位学生是否能够在第R次提问时排除头上的数为的情况。
找出问题的前提，即已知条件：
1) 某两个数的和等于第三个
2) 每个人的纸条上都写了一个大于0的整数
每个人头上的数不是另两数的和就是另两数的差。由于不能直接判断一定是其中某个数，就只能采取排除法.由于他们不会猜错，因此在下面只需考虑他们如何能够排除头上数不同于实际的可能情况。
考虑四元组,设i,j满足，则第k位学生头上的有两种情况或.其中,不能直接排除。由于，所以当且仅当能够直接排除这种情况.即,其中。
显然，，因此。注意到集合与的定义,显然，因此必然有。
考虑四元组，即第k位学生不能直接猜出自己头上的数，就需要通过推理来排除头上数的两种情况中的一种。当第k位学生假设自己头上是某数，并通过推理发现别人理应能够在前两次提问中最先猜出头上的数，就可以根据实际上别人并没有猜出这一矛盾来排除其中一种情况。（可以参考前面例子中对C思想的分析)
显然三位学生都不可能通过推理排除自己头上数的实际情况（因为他们是永远不会猜错的）。所以下面仅需考虑如何排除头上数不同于实际的另一种情况.
对于四元组，为了讨论方便，不妨设.
注:下面的为析取符号,即
1) 当k=1时

2) 当k=2时

3) 当k=3时

对于四元组，设i,j满足，，。 当时，,当时，。
1. 当时，设,当时，设。
2. 当时，设,当时，设.
由上面定义可得

分别考虑四元组和两种情形：
1) 当，有，则。由于，第k位学生须通过推理排除头上数为的情况。
若满足，记。满足,，则可以得到或,因此或。，因此，，而,，矛盾。
结论:对，。
2) 当，且。有，，第k位学生须通过推理排除头上数为的情况。由于，显然。
由前面讨论1）可推得
a) 当,即,,。因此，.
b) 当,即，,。因此，。
我们可以从考虑四元组，变为考虑四元组或。这样就形成了一个线性的推理方式，而非先前分支庞大的推理方式。
由于可以只考虑,若，可以转而考虑四元组或.由于三个数不可能无穷的递减,因此在有限次转化后必然达到“终结情形”.
结论：无论三个数如何变化，无论从谁开始提问，必然是头上数最大的人最先猜出自己头上的数。
由上述结论，对于，可以定义的递推式:
1) 当k=1时
1. 当时，
2. 当时，
3. 当时，
2) 当k=2时
1. 当时，
2. 当时,
3. 当时，
3) 当k=3时
1. 当时，
2. 当时,
3. 当时，
由于我们只考虑,因此k可由三个数直接确定，因此可以简化为。
利用上面的公式,通过计算机编程来解决问题.参见源程序1。
由于建立了线性的递推关系，因此避免了问题规模随着提问次数呈指数型增长。有效的解决了问题，其解决方法是建立在对问题的深入分析之上的。现在让我们总结解决问题中思路的主线：
提炼重要的前提条件→考虑何种情形为“终结情形"→对非“终结情形”建立推理的等价关系→考虑何种情形能归结到“终结情形”→分情况讨论并加以证明→得出结论并改写等价关系→得出公式
整个过程是从分析问题的本质入手，而非一味单纯地从每个人思想出发，并推导出普遍意义的结论。从综观全局的角度分析问题，避免了最烦琐的“思维嵌套”，并且使得问题规模从指数型转变为线性。

二、第一种推广
问题描述：
一位逻辑学教授有n名非常善于推理且精于心算的学生。有一天,教授给他们n人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个大于0的整数，且某个数等于其余n-1个数的和。于是，每个学生都能看见贴在另外n—1个同学头上的整数，但却看不见自己的数.
教授轮流向n发问：是否能够猜出自己头上的数。经过若干次的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。
我们的问题就是：证明是否一定有人能够猜出自己头上的数,若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数,分析整个推理的过程,并总结出结论。
我们对n=3时的定义加以修改：
定义：
定义1： 用n+1元组，，来描述推理过程中的一种情形，其中n个人头上数分别为，从第一位学生开始提问，且当前的被提问者为第k位学生。
性质：对于n+1元组，第k位学生可以不依靠别人的回答进行推理，能够直接判断出自己头上数，并称n+1元组描述的情形为“终结情形”。
性质：对于n+1元组，，并称n+1元组描述的情形为“一类情形”。
性质：对于n+1元组，，并称n+1元组描述的情形为“二类情形”。
定义2：集合.
定义3：集合。
定义4：集合。
定义5：若对于n+1元组
1) 若第k位学生不能够猜出头上的数，记。
2) 若第k位学生能够猜出头上的数,记为从第一位学生开始提问直到猜出头上的数的过程中总共的提问次数。
定义6:对于n+1元组，记(表示真或假），，表示当三位学生头上的数分别为，第k位学生是否在恰在第R次提问时最先猜出头上的数为。
定义7：对于n+1元组，记（表示真或假），，表示当三位学生头上的数分别为,第k位学生是否能够在第R次提问时排除头上的数为的情况。
定义8:对于，记,。
对于，，。。所以对第k位学生而言，头上的数可能有两种情况：（当时）或(当时）。
考虑.由于，不能直接排除。而当且仅当时,能够直接排除这种情况.即。
对于，即。若有，，其中，则必然有，矛盾。所以除第k位学生外剩下学生中仅有第v位学生头上的数。
当第k位学生假设自己头上是某数，并通过推理发现别人理应能够在前n—1次提问中最先猜出头上的数,就可以根据实际上别人并没有猜出这一矛盾来排除其中一种情况。
1) 当时,即，因此第k位学生需排除头上数是.令,
2) 当时，即，因此第k位学生需排除头上数是。令，
与n=3时的问题原形类似,可以得到如下式子：

注：上面总共n-1项，其中不含

分别考虑和两种情形:
1) 当，有，则。由于,第k位学生须通过推理排除头上数为的情况。
若满足，记。满足, ,，.因此，而,矛盾。
结论：对,.
2) 当，且。有，，第k位学生须通过推理排除头上数为的情况。此时有,因此。
由前面结论1）推得
由于，。当时,有，由上述结论得.因此。
我们可以从考虑，变为考虑。这样就形成了一个线性的推理方式，而非先前分支庞大的推理方式.

由于可以只考虑，若,可以转而考虑，。由于n个数不可能无穷的递减,因此在有限次转化后必然达到“终结情形”。
结论：无论n个数如何变化，无论从谁开始提问，必然是头上数最大的人最先猜出自己头上的数.
由上述结论,对于，可以定义的递推式：
1) 当时，
2) 当时
设,其中，
a) 当v<k时，
b) 当v〉k时，
由于我们只考虑，因此k可由n个数直接确定，因此可以简化为。
利用上面的公式，通过计算机编程来解决问题.参见源程序2。
至此,第一种推广情形就解决了。可以发现n=3时情形的证明,对解决一般情形提供了很好的对比，使得我们能够较为轻松地解决问题，这其实也是建立在对n=3时的情形的分析之上的.

三、第二种推广
问题描述：
一位逻辑学教授有n名非常善于推理且精于心算的学生。有一天，教授给他们n人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个大于0的整数,并将他们分成了两组（一组学生有m人，且，且学生并不知道如何分组），且两组学生头上数的和相等。于是，每个学生都能看见贴在另外n-1个同学头上的整数,但却看不见自己的数.
教授轮流向n发问：是否能够猜出自己头上的数。经过若干次的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。
我们的问题就是：证明是否一定有人能够猜出自己头上的数，若有人能够猜出，则计算最早在第几次提问时有人先猜出头上的数，分析整个推理的过程，并总结出结论。
由于当n=3时,m只可能为2,即为问题原形，而对于m=n—1，即第一种推广情形.因此在下文只讨论n>3，m<n—1时的情形.
对于每个人判断自己头上的数，依据分组情况不同,头上的数就可能不同。
对，第k位学生可以看见除自己外所有学生头上的数，并假设在某种分组情况下，可以计算出与自己不同组的学生头上数的和，由题目条件“两组学生头上数的和相等”,可以计算出自己头上的数。由于有种分组情况，因此相对应头上的数有种（其中可能也包括了一部分重复的数及非正整数）.

定义：
定义1： 用n+1元组,,来描述推理过程中的一种情形，其中n个人头上数分别为，从第一位学生开始提问，且当前的被提问者为第k位学生。
性质：对于n+1元组，第k位学生可以不依靠别人的回答进行推理，能够直接判断出自己头上数,并称n+1元组描述的情形为“终结情形”。
性质：对于n+1元组，,并称n+1元组描述的情形为“一类情形"。
性质:对于n+1元组，，并称n+1元组描述的情形为“二类情形”。
定义2:集合。
定义3:集合。
定义4：集合。
定义5：若对于n+1元组
1) 若第k位学生不能够猜出头上的数，记.
2) 若第k位学生能够猜出头上的数，记为从第一位学生开始提问直到猜出头上的数的过程中总共的提问次数。
定义6：对于n+1元组，记(表示真或假），,表示当三位学生头上的数分别为，第k位学生是否在恰在第R次提问时最先猜出头上的数为。
定义7：对于n+1元组，记(表示真或假）,,表示当三位学生头上的数分别为，第k位学生是否能够在第R次提问时排除头上的数为的情况.
定义8：对于,记，。
定义9：对于，用X指代第k位学生推测的任意一种分组情况。定义为第k位学生假设分组X情况下两组学生头上数的和。
定义10：对于，当第k学生在考虑某一可能分组的情况下，记为所推测出的头上数的可能值。
定义11：对于，定义，其中。
定义12：对于，定义分组T：选取第位学生为一组，剩下的学生为另一组（第k位学生在这一组）.则
对于,考虑分组T的情况， ,显然(第一个求和符号有m项,第二个求和符号有n—1—m项,由于，且）.
对于任意一个分组X,设
1) 当与第k位学生不同组的学生有m人时，设（m项)。
显然有

2) 当与第k位学生同组的学生有m人时，设（n—m项)。
显然有

考虑的条件：
I. 当。
考虑在分组T的情况下，，这种情况不同于实际情况，需要进行推理。得到结论:,.
II. 当。
考虑实际分组B的情况
1) 当与第k位学生不同一组的学生有m人时,。在分组T的情况下，有。
2) 当与第k位学生同一组的学生有m人时，.当时,即为上面一种情况，因此只考虑
在分组T的情况下，有。
要使得，必然要满足。因此实际分组B只可能是上面第一种情况，且满足,显然，因此可得，即。
显然,在此条件下，若存在可能的分组C满足，。显然由于,必然有，即。
若不存在可能的分组C满足，即任意分组,则。
进一步分析对可能的分组C满足，何时满足。分两种情况考虑:
1) 当不全相等时，必然有，考虑如下分组C：第位学生为一组，第位学生为一组，此时显然有。
需满足，即，因此.另一方面，，而，因此，矛盾。因此，。
2) 当全相等时,不妨设,，.
考虑分组C：m个头上数为q的学生为一组，剩下的学生为一组（第k位学生在这组中)。
由于,即，因此。
1. 当时，再来考虑分组D：头上数是p的学生与n-m-1个头上数是q的学生在一组， 剩下学生为一组。由于，因此。
由于,因此，因此，观察得到的两个不等式，显然矛盾，因此当时，。
2. 当时，可以得到，且.
因此,的条件为：
1.
2. 或

分情况进行讨论的情况：
I. 对于
若,，记.满足,。
若第k位学生能够猜出自己头上的数，则他一定要通过推理排除头上数所有可能情况中与实际不相等的值。
由于，即,因此。考虑分组T的情况, ，因此需要排除这种情况。令。

注：上面为代定变量，显然有,由于具体值与结论无关,因此不必讨论。
1) 当
则可得。，使得，,而，矛盾。
因此得到结论：对于,若在分组T的情况下满足，则。
2) 当
由于，因此等号成立的条件为，由于，因此仅当存在这种情况，此时。
1. 若
考虑实际分组B的情况,显然,，此时。
2. 若
显然，对，。
若，,，而，矛盾。
因此。
设，。
由于，对第k位学生只有两种本质不同的分组情况,即第k位学生与第位学生在同一组或不在同一组，两种情况对应头上数的可能值分别是：
及
设,对，第位学生只有两种本质不同的分组情况，两种情况对应头上数的可能值分别是:
及
设, 。

显然，对，。
若，，,而，矛盾。
因此
考虑，,，对第k位学生只有两种本质不同的分组情况，两种情况对应头上数的可能值分别是：
及
设，且， 。

定义：
显然
当只有两种本质不同的分组情况时，排除其一即可猜出头上的数，利用上述结论讨论。
a) 当

b) 当

由于,,，，因此对，只有第k位学生和第位学生两人可能最先猜出头上的数。
对第位学生也只有两种本质不同的分组情况,即第k位学生与第位学生在同一组或不在同一组，两种情况对应头上数的可能值分别是：
及
设, 。
比较后可发现，

由于对第位学生只有两种本质不同的分组情况,因此排除其一即可猜出头上的数，即。
因而
显然
则说明第位学生将在第k位学生之前猜出头上的数,说明，矛盾。
得到结论：对于，若在分组T的情况下满足，则。

因此综合考虑上述所有情况，得到结论：对于，。
II. 对于
并非所有，第k位学生都能猜出头上的数,下面举一个例子:
当时,考虑(实际分组为1,3，3为一组，1,2，4为一组），对于第6位学生须排除头上数是6的可能（分组为2，3，3为一组,1,1，6为一组）,记，，由前面结论可得，而，，即。因此，即第6位学生不能最先猜出头上的数。而，,考虑到前面讨论Ⅰ，因此没有人能猜出头上的数。
由于对于能够猜出头上数的情形，在形式上不具特殊性，因此我们只有在推理过程中不断判定是否有可能猜出头上的数。
对于，若,则分组T的情况下，,,则，，由前面讨论Ⅰ可得。显然有，因此判定条件之一为。
可能有多个学生头上的数同为最大数，若有多个学生头上的数同为最大数,则。下面分情况讨论：
1. 当或
则分组T的情况下，,由前面的判定条件，在这种情形下，第k位学生不能够最先猜出头上的数。
当,利用前面结论可知第位学生不能够最先猜出头上的数。而当，。因此没有人能猜出头上的数。
2. 当，
a) 若，此时即为第1)种情况。
b) 若,则所有n个数都相等，此时。
3. 当，，
显然当n为奇数时，必然有，即第1)种情况。因此下面只考虑n为偶数。
a) 若，此时即为第1）种情况。
b) 若
对第k位学生只有两种本质不同的分组，不妨设，。
i. 若，。
ii. 若，考虑须排除的情况，，令。
显然,

考虑，则,令。
显然,。观察,可以发现即为第1）种情况.因此，第k位学生不能够最先猜出头上的数.
当，利用前面结论可知第位学生不能够最先猜出头上的数。而当，。因此没有人能猜出头上的数。
4. 当，且
则必然有，显然可以得到，不妨设，，并称这种两两相等的情形为“A类情形”。
对第k位学生只有两种本质不同的分组方式，考虑须排除的情况，。
显然，

对第位学生只有两种本质不同的分组方式，考虑须排除的情况，。又回到了“A类情形”
又由于四数中始终有一个数在减小，因此有限次推理之后,必然达到“终结情形”，此时满足条件为。
因此一定有人能够猜出头上的数。但具体由第k位学生和第位学生中哪一人最先猜出头上的数需要具体计算后才能确定.
至此，讨论完所有存在两个以上的学生头上为最大数的情形。

可能的分组C满足，进行讨论。
在这种情况下，。令。
1) 当时
，，由前面讨论Ⅰ可得。因此第k位学生不能够最先猜出头上的数。由,因此，.因此没有人能够猜出头上的数.
2) 当时
此时，可以利用前面对多个学生头上数同为最大数时的讨论的结果：
1. 当（讨论多个最大数时的讨论1)
对，考虑,第i位学生不能够最先猜出头上的数。即没人能猜出头上的数。因此，对于，第k位学生不能够最先猜出头上的数。
2. 当,（讨论多个最大数时的讨论2）
a) 当
对，考虑，第i位学生不能够最先猜出头上的数。即没人能猜出头上的数。因此,对于，第k位学生不能够最先猜出头上的数。
b) 当
由于，因此可以得知，即。
3. 当，，（讨论多个最大数时的讨论3）
a) 当
对，考虑，第i位学生不能够最先猜出头上的数，即没人能猜出头上的数。因此，对于，第k位学生不能够最先猜出头上的数.
b) 当
不妨设,。
i. 当
可以由之前讨论得到，于是第k位学生头上的数仅有一种可能情况,不属于讨论的范围。
ii. 当
对，考虑,第i位学生不能够最先猜出头上的数，即没人能猜出头上的数。因此，对于，第k位学生不能够最先猜出头上的数。
4. 当,且（讨论多个最大数时的讨论4)
显然可以得到,此时不存在实际划分B，使得，即这种情况不属于讨论的范围。
3) 当时
，因此,第k位可能最先猜出头上的数，因此需要继续推理。

结论:对于,第k位学生可能最先猜出头上的数，需要继续推理的判定条件为：，即，且对任意可能分组C符合，满足.
当，考虑
1) 当，由前面讨论多个最大数时的讨论4，及，一定有人能够猜出头上的数.
2) 当，显然，因此，即。第k位学生头上数其余两种可能值，，。由前面结论，需要继续推理。
由于仅有这两种情况,即不存在情况使得没有人能够猜出头上的数。且推理时四个数始终在减小，因此经过有限次推理之后,必然达到“终结情形”。
而对于第一种推广情形，即，必然有人能猜出自己头上的数。
因此时的一切情况，必然有人能猜出自己头上的数。
由于现在的推理在加强判定的情况下，依然可能出现多种考虑情况.所以推理已不是线性的推理，整个推理过程将成为树状结构。
由于分组情况繁多，而且判定方式也比较复杂,因此这时计算的值已经非人力能够解决，但是已经可以编程解决问题了,参见源程序3。

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

参考文献
《CTSC2001分析》
《算法与数据结构》 傅清祥 王晓东 编著
第19页 共19页