数学科普

孙庞猜数（上）

作者：安迁

一、题目

我在网上第一次看见这道数学趣味题时，它叫孙庞猜数：

孙膑和庞涓是鬼谷子的徒弟。一天鬼谷子出了这道题目：他从2到100中选出两个（不一定不同的）整数，把两数之和告诉庞涓，把两数之积告诉孙膑。

庞涓说：“我虽然不能确定这两个数是什么，但是我肯定你也不知道这两个数是什么。”

孙膑说：“我本来的确不知道，但是听你这么一说，我现在能够确定这两个数字了。”

庞涓说：“既然你这么说，我现在也知道这两个数字是什么了。”

问：这两数是什么？

这道题目最早由德裔荷兰数学家Hans Freudenthal于1969发表于荷兰数学杂志Nieuw Archief voor Wiskunde。Hans Freudenthal的原题中的人物当然不是鬼谷子、孙膑和庞涓，而且在数学意义上和我上面所说的也略有不同，其中规定两个数必须不同，而且知道两数和必定小于等于100（我们将要看到这其实并不使题目简单多少）。 马丁·加德纳在1979年听说了此题，将其发表在他著名的《科学美国人》数学专栏上，并称其为“不可能问题”，因为这题看起来似乎缺少了一些条件，不可能解得出来。

所以现在这个问题被称为“Freudenthal问题”，“不可能问题”或“和与积问题”。此篇文章中则称其为“孙庞猜数问题”。题目里被问到的人是孙膑和庞涓，或者更一般地说，是“非常聪明，推理迅速，逻辑无懈可击，没有绝对把握不会乱说话，只说真话的人”，而且他们对此都清楚。这其实是一个不可或缺的条件，否则这题就真的不可能解了。在本文中谈到的所有的题目中，我们都假设这个条件成立，不再强调。

二、比较简单的题目

为了解释孙庞猜数问题的解法，先解决一个此类问题中比较简单的，也许是个好主意。

这类简单问题往往猜的是扑克牌或生日。因为扑克牌有花色与点数两个性质，知道花色点数则扑克牌确定；而生日则有月份与天号两个性质，知道月份天号则生日确定。这同孙庞猜数问题中的两个数有和与积两个性质，知道两数和与积，则两数确定的情况是一样的。（如果知道两数和为S，积为P，那么这两数就是一元二次方程 x2-Sx+P=0的两个根。）这里举一个猜生日的例子。

2015年4月10日，新加坡电视节目主持人江坚文在自己的Fackbook网页上贴了一道新加坡及亚洲中学奥数竞赛的题目，在网上热传，许多媒体也报道了此事。

江坚文贴的奥数题，图片来自网络
江坚文贴的奥数题，图片来自网络

题目翻译如下：

两个男孩Albert和Bernard刚和女孩Cheryl成了朋友，他们想知道她的生日。Cheryl给了他们10个可能的日期：

5月15日，5月16日，5月19日，
6月17日，6月18日，
7月14日，7月16日，
8月14日，8月15日，8月17日

然后Cheryl分别单独地把她生日的月份和天号告诉了Albert和Bernard。

Albert说：“我不知道Cheryl的生日是哪天，但是我知道Bernard也不知道。”

Bernard说：“我本来不知道Cheryl的生日是哪天，但是现在我知道了。”

Albert说：“那我也知道Cheryl的生日是哪天了。”

所以Cheryl的生日是哪天？

容易看出，这个题目和孙庞猜数问题的形式是类似的。

如果我们把Cheryl给出的十个可能的生日日期按照月份和天号分类写成一个交叉表：

  14日 15日 16日 17日 18日 19日
5月   O O     O
6月       O O  
7月 O   O      
8月 O O   O    

表中有O的那些日子是Cheryl可能的生日。

解题时必须分清楚什么是Albert当前知道的，Bernard当前知道的，和我们（解题人）知道的。

当Albert说第一句话时，我们知道：他知道Cheryl的生日的月份，但不知道Cheryl的生日是哪天。所以要划去所有那些行中只有一个可能值的那些行。不过对于这题来说，这样的行并不存在，所以此处不划去任何行。

而且Albert还知道他说话前Bernard也不知道Cheryl的生日是哪天。这意味着什么？这意味着Cheryl生日的月份不可能是5月或6月。因为如果Albert知道的月份是5月或6月，那么他就不敢说Bernard也不知道Cheryl的生日——如果Cheryl的生日是5月19日或6月18日，Cheryl告诉Bernard的天号就会是18日或19日，而对应这两个天号的日子都分别只有一个，不需要月份也能知道是哪天。Albert的这句话让我们划去所有那些列中只有一个可能值时，那些值所在的行。18日和19日两列中都分别只有一个值，那么要划去这些值所在的行，也就是5月和6月：

  14日 15日 16日 17日 18日 19日
5月   O O     O
6月       O O  
7月 O   O      
8月 O O   O    

而Bernard听了这句话，也能得出同样的结论。不仅如此，他比我们还多知道一个天号，于是他说“现在我知道了”。这意味着，上面这张划过的表，加上他所知的天号，就能得出Cheryl生日的唯一可能。所以Cheryl生日的天号不可能是14日，否则此时Bernard无法区别月份是7月还是8月。Bernard的这句话让我们在已经划过的表中，划去所有那些其中有超过一个可能值的列。14日就是这样一列：

  14日 15日 16日 17日 18日 19日
5月   O O     O
6月       O O  
7月 O   O      
8月 O O   O    

Albert听完Bernard的话后，也能得出同样结论。不仅如此，他比我们还多知道一个月份号，于是他说“我也知道了”。这意味着，上面这张划过的表，加上他所知的月份号，就能得出Cheryl生日的唯一可能。和上面Bernard说“知道了”类似，这让我们在已经划过的表中，划去所有那些其中有超过一个可能值的行。8月是这样的一行：

  14日 15日 16日 17日 18日 19日
5月   O O     O
6月       O O  
7月 O   O      
8月 O O   O    

剩下来唯一的日子是7月16日，于是，我们也知道了Cheryl的生日。

三、解法总结，孙庞猜数问题的算法解

通过上节的例子，看得出此类问题的解决方式很简单。

  • 1) 选定第一个说话的人知道的那个性质为行，另一人知道的性质为列，排出交叉表，并填入所有可能值。（哪个为行哪个为列当然无所谓，但如果选取的方式和这里不同，下面的行/列说法也要反过来了。）
  • 2) 划去所有那些其中只有一个值的行。（对应第一句说“我不知道”。）
  • 3) 划去所有那些列中只有一个可能值时，那些值所在的行。（对应第一句说“我知道你不知道”。）
  • 4) 划去所有那些其中有超过一个可能值的列。（对应第二句说“我知道了”。）
  • 5) 划去所有那些其中有超过一个可能值的行。（对应第三句说“我知道了”。）表中剩下的值就是所有可能的解。
  • 6) 如果只剩下一个值，那么我们（解题人）也知道了答案，解决了这个问题。

上面这个解法步骤对每一步需要做的事情的描述非常明确。事实上它描述了一种算法，很适合编个程序叫电脑来做。

于是用计算机程序很容易解决本文开头的孙庞猜数问题。无非就是建一个200行（对应从1到200的两数和值。虽然和值不可能是1，2或3，但是多设几个空行并无所谓。列的情况类似），10000列（对应从1到10000的两数积值）的交叉表划上一通。对电脑来说处理这么大小的表轻而易举。

四、变化过的解法

但如果我们想用手算的方法来解决孙庞猜数问题，上面这个直接暴力的方法就不容易做了。所以这里要将前面的解法变动一下。

回到Albert说完“我不知道Cheryl的生日是哪天，但是我知道Bernard也不知道。”这句话后我们得到的表格：

  14日 15日 16日 17日 18日 19日
5月   O O     O
6月       O O  
7月 O   O      
8月 O O   O    

按照上面的算法，接下去根据Bernard的话“现在我知道了”，我们会划去所有那些其中有超过一个可能值的列。但让我们假装目前我们看不出这一步只会划去14日这一列，而只是知道有些列被划掉了。

接下去根据Albert的话“现在我也知道了”，我们会划去所有那些其中有超过一个可能值的行。我们可以证明，8月就是这样的一行：在上面这个表中，我们可以找到8月15日和8月17日两个值（日子），它们所在的列都只有一个值，所以这两列是不会在刚才“划去所有那些其中有超过一个可能值的列”的过程中被划去的。所以目前8月这一行必定保留着这两个日子，于是在本步骤里必被划掉。

现在我们只剩下了7月14日和7月16日这两个日子。但7月14日我们验证一下，发现在前面这个表中它所在列有两个值，所以会被Bernard的那句话划掉。于是只剩7月16日这个值，经过验证，在前面这个表中它所在列只有一个值，所以不会被Bernard的那句话划掉。所以7月16日就是Cheryl的生日。

总结一下，变化过的解法如下：

  • 1) 选定第一个说话的人知道的那个性质为行，另一人知道的性质为列，排出交叉表，并填入所有可能值。
  • 2) 划去所有那些其中只有一个值的行。
  • 3) 划去所有那些列中只有一个可能值时，那些值所在的行。将划完后的表格称作X。
  • 4’) 如果在X的某行里可以找到两个值，它们所在的列都分别只有它们这一个值，划去此行。
  • 5’) 对这些行中的每个值讨论（运气好的话，你会发现整个表中只剩下很少几行了，也许只有一行），看表X中它所在的列里是否有多于一个的值，如果是，那么它就不可能是解；如果否，它就是一个可能解。
  • 6) 如果只剩下一个可能解，那么我们（解题人）也知道了答案，解决了这个问题。

容易看出，这个解法和前面那个是等价的：前三步和原解法一致；第5’步是将前一种方法的4和5放在一起，原本整列整行划去的方式换成了逐个值讨论的方式。理论上说，这里就算没有第4’步也同样能得到解；第4’步的用处在于可以划掉许多在前一种方法的第5步必定会划去的行，减少第5’步中需要讨论的值的个数。这个解法的特点是不实际动手划列，只是实际动手划行，然后对剩下的值逐个讨论，看看它是否会在划列的那一步被划掉。对于解猜生日的题目，这显然是个不必要的复杂方法，因为实际动手划列也很容易。但是对于孙庞猜数问题，划列较难，所以用这种解法能节省讨论的规模。

五、孙庞猜数问题的手工解法

对应于解法的第1步，建一个200行（对应从1到200的两数和值），10000列（对应从1到10000的两数积值）的交叉表，前面所说的“值”是所有形如(x,y)的数对（我们并不考虑两数的次序，所以(x,y)和(y,x)算作是同一个数对），都可填入表中唯一的一格，而表中的每一格，最多只会有一个数对填入。和为1，2，3的那些行都是空的；积为素数，或是分解成两数之积后，其中有一个数必大于100（比如11*13*17=2431）的那些积的列也是空的。这个大表真的全写出来不切实际，得建在我们的脑子里。

庞涓知道的是行号即两数和S，孙膑知道的列号即两数积P。

A) 庞涓的第一句话

对应于解法的第2步，据庞涓说的“我虽然不能确定这两个数是什么”，我们得划去所有那些只有一个数对的行，也即199=99+100和200=100+100这两行，因为它们都只有一种分解为小于等于100的两数和的可能。

对应于解法的第3步，据庞涓说的“但是我肯定你也不知道这两个数是什么”，我们得划去所有列（即乘积）中只有一个可能数对（即乘积的乘法分解只有一种）的那些数对所在的行（所有两数和同这个乘法分解后的两数和相等的数对都要划掉）。

首先，可以划掉那些和数可以表示为两个素数和的那些行。如果庞涓知道的S=p+q，其中p和q都是素数，庞涓就没法保证鬼谷子选的两个数字不会恰好是p和q。如果鬼谷子选的两个数字恰好就是p和q，孙膑知道的积P=p*q；他只要对P进行乘法分解得到唯一可能的乘积形式p*q，便知道了数对(p,q)。于是庞涓就不敢贸然说“但是我肯定你也不知道这两个数是什么”这种话。也即，因为(p,q)这个数对所在的p*q=P这一列里只有这一个数对，所以p+q=S这行必须划去。

这样，所有偶数行都被划去了：根据哥德巴赫猜想，任何大于2的偶数都可以表示为两个素数之和，对200以内的偶数，猜想肯定被验证过。

形为S=2+p的奇数，其中p是奇素数的那些S也同样要划掉，因为2是素数。

其次，如果和54<S<54+100，那么S可以写为S=53+a，a≤100。如果鬼谷子选的两个数字恰好是53和a，那么孙膑知道的积P就是P=53*a，任何其他的分解方式都会造成其中一个数大于100。这样的S对应的行也要划去。如果54+100≤S≤97+100，那么S可以写为S=97+a，a≤100。97是一个素数，同以上推理，这样的S对应的行也要划去。

再次，S=51也要排除掉，因为51=17+2*17。如果鬼谷子选的是(17,2*17)，那么孙膑知道的将是P=2*17*17，他对鬼谷子原来的两数的推测只能是(17,2*17)。

在这里插一句，上面这第一个步骤我们就去除了所有和为偶数或是大于54的情况，把问题就变回到Freudenthal原题规定两个数必须不同（两数相同和必为偶），而且一开始就知道和必定小于等于100的约束以内。所以本文这题并不比Freudenthal原题的难度高多少。

把4到54间，不是形如2+p（p为素数）的奇数，又不是51的所有数梳理一遍，现在我们这个大表中只剩下11，17，23，27，29，35，37，41，47以及53这些行了。

B) 剩下的行

我们还得保证，只要庞涓知道的S在上面这些数中，他就可以说“但是我肯定你也不知道这两个数是什么”。否则如果我们忘了划某条应该划掉的行，接下去我们和孙膑的推理就不站在同条线上，于是就站不住脚了。

令C为剩下的行号的集合，也即C={11, 17, 23, 27, 29, 35, 37, 41, 47, 53}。

上面“划掉所有可表示为两素数和的行”一步，保证了C中任意数S无论怎么拆成两数和，都至少有一个数是合数；而“划掉所有偶数”一步，让它们必是一偶一奇。所以S只能拆成

  • S=2+a*b，或
  • S=a+2n*b。

这两个样子，其中a和b都是奇数，n>=1。那么（当下面我说到“至少两组数”中的两组数都不相同，而且的确存在（也就是那些数都小于100）的理由我就不写了，根据条件很显然）：

  • 或者孙膑的P=2*a*b，孙膑就会在(2*a,b)和(2,a*b)至少两组数里拿不定主意（a和b都是奇数，所以这两组数一定不同）；

  • 或者P=2n*a*b，

    • 如果n>1，那么孙膑就会在(2n-1*a,2*b)和(2n*a,b)至少两组数里拿不定主意。
    • 如果n=1，而且a不等于b，那么孙膑就会在(2*a,b)和(2*b,a)至少两组数里拿不定主意；
    • 如果n=1，而且a等于b，这意味着S=a+2*a=3*a，所以S一定是3的倍数，上面这些数里只有S=27是3的倍数，我们只要讨论它就可以了。27如果被拆成了9+18，那么孙拿到的P=9*18，他就会在(9，18)和(27,6)至少两组数里拿不定主意。

“拿不定主意”也即P列必定超过2个数对，这些数对所对应的行当然不可划去。

现在我们知道，当且仅当庞涓得到的和数S在C={11, 17, 23, 27, 29, 35, 37, 41, 47, 53}中时，他才会说出“我虽然不能确定这两个数是什么，但是我肯定你也不知道这两个数是什么”这句话。这些行不能被划去。在改动过的解法第3步中我们说到的表X，就是由上述这些行组成的。

C) 孙膑的话

孙膑的话“我现在能够确定这两个数字了”表明，将P分解成两数之积，得到关于鬼谷子的那两个数的若干个推测中，有且仅有一个推测的两数之和在C中。否则的话，他还是会在多个推测之间拿不定主意。我们要划去所有那些可以分解成两种以上积形式，而且分解后的和在上面这个集合C中的那些P列。但是我们在这里使用改动过的解法，就不实际地执行这个步骤了。

不过我们在这里可以先看看，哪一些列是一定不会被划去的。

形如P=2n*p，其中n>1，p为奇素数的那些列是不会被划去的。如果孙膑手里有P=2n*p，他就知道唯一可能的数对是(2n,p)，因为除此之外，P的其他分解成两数积的方式必定会是两个偶数，而这些数对所在的行（和为偶数）都已经在前3步里被划去，不在表X里了。所以列P中只剩下(2n,p)这个数对，不会被划去。

下面再举不会被划去的几列，当然它们不是随便举的，这几列都会在下面被用到。

第2*33=54列不会被划去。因为它分解成两数之积只可能是(2,33)=(2,27)，(2*3,32)=(6,9)或(2*32,3)=(18,3)，而后面两个数对的和分别等于15和21，都不在集合C中，所以也不在表X中，孙膑可以排除。也即如果孙膑知道的两数之积为54时，他就确定那两数只能是(2,27)，并说“我知道了”。

第22*52=100列不会被划去。因为它分解成两数之积只可能是(2,2*52)=(2,50)，(22,52)=(4,25)，(22*5,5)=(20,5)或(2*5,2*5)=(10,10)。只有(4,25)这一对的和29在C中。

第2*3*47=282列不会被划去。因为它分解成两数之积只可能是(2,3*47)=(2,141)，(2*3,47)=(6,47)和(2*47,3)=(94,3)。只有(6,47)这一对的和53在C中（第一对中的141已经超出题目要求的100以内的数）。

第2*5*31=310列不会被划去。因为它分解成两数之积只可能是(2,5*31)=(2,155)，(2*5,31)=(10,31)和(2*31,5)=(62,5)。只有(10,31)这一对的和41在C中。

D) 庞涓的第二句话

对应于解法的第4’步，如果C中的某个S能用两种方法拆成S=a+b和S=a’+b’，而且a*b和a’*b’都能被孙膑唯一地分拆出来的话，也即第a*b和第a’*b’列都未在上一步C)中被划去的话，那么这行S就应被划去。

比如S=11就是这样应被划去的一行。因为11=22+7=23+3，这是两种把S拆成2n+p，其中n>1，p为奇素数的方法。按照上面C)中的讨论，22*7和23*3这两列都不会被划去。所以S=11这行应被划去。

类似地，
23=22+19=24+7
27=22+23=24+11
35=22+31=24+19
37=23+29=25+5
47=22+43=24+31
这些行都应被划去。

于是S的可能值只能在{17 29 41 53}中。让我们继续缩小这个表。

我们有29=2+27=4+25。根据C)中讨论，第2*27=54列和第4*25=100列都未被划去，所以S=29应被划去。

同样41=22+37=10+31。根据C)中讨论，第22*37列和第10*31=310列都未被划去，所以S=41应被划去。

类似地53=24+37=6+47，这行也应被划去。

E) S=17

现在只剩下第17行。对应于解法的第5’步，我们得考虑17的所有两数和拆法。对每种拆法，我们要看在表X中它所在的列里是否有多于一个的数对，如果是，那么就必须排除这种可能。换句话说，如果17被分拆成17=a+b，而孙膑手里的两数之积P就是P=a*b，可是P还有另一种分解法P=a’*b’，而且a’+b’也在C中，那么，孙膑的“我现在能够确定这两个数字了”这种话就说不出来了，他无法区别(a,b)和(a’,b’)两种情况。

逐个来看：

(2,15)：那么P=2*15=6*5，而6+5=11也在C中。排除这种可能。

(3,14)：那么P=3*14=2*21，而2+21=23也在C中。排除这种可能。

(4,13)：那么P=4*13=2*2*13。孙膑一开始可以猜的组合是(2,26)(4,13)，等庞涓说过“但是我肯定你也不知道这两个数是什么”，让孙膑确信两数和只可能在C中时，他发现只有(4,13)这种分解成立。这是一个可能的解。

(5,12)：那么P=5*12=3*20，而3+20=23也在C中。排除这种可能。

(6,11)：那么P=6*11=2*33，而2+33=35也在C中。排除这种可能。

(7,10)：那么P=7*10=2*35，而2+35=37也在C中。排除这种可能。

(8,9)：那么P=8*9=3*24，而3+24=27也在C中。排除这种可能。

于是我们得到了唯一解(4,13)。只有这种情况，才可能出现孙庞猜数问题中的对话。于是我们知道，鬼谷子的两个数是4和13。

参考文献：

[1] Axel Born, Cor A.J. Hurkens, Gerhard J.Woeginger, The Freudenthal problem and its ramifications (Part I). Bulletin of the European Association for Theoretical Computer Science, EATCS, 90, Pages 175-191. (2006).

[2] ​Martin Gardner, Mathematical Games: A Pride of Problems, Including One That Is Virtually Impossible, Scientific American, 241, pages 22–30. (1979)

[3] When is Cheryl’s birthday? Singapore math question for kids stumps internet. CBC网站

（下）>