猜数问题的研究
??????,?,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页