猜数问题的研究
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) 当v
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页