征四夷打數字?我在網上第一次看見這道數學趣味題時，它叫孫龐猜數：，今天小編就來聊一聊關于征四夷打數字?接下來我們就一起去研究一下吧!

征四夷打數字

一、題目

我在網上第一次看見這道數學趣味題時，它叫孫龐猜數：

孫膑和龐涓是鬼谷子的徒弟。一天鬼谷子出了這道題目：他從2到100中選出兩個（不一定不同的）整數，把兩數之和告訴龐涓，把兩數之積告訴孫膑。

龐涓說：“我雖然不能确定這兩個數是什麼，但是我肯定你也不知道這兩個數是什麼。”

孫膑說：“我本來的确不知道，但是聽你這麼一說，我現在能夠确定這兩個數字了。”

龐涓說：“既然你這麼說，我現在也知道這兩個數字是什麼了。”

問：這兩數是什麼？

這道題目最早由德裔荷蘭數學家Hans Freudenthal于1969發表于荷蘭數學雜志Nieuw Archief voor Wiskunde。Hans Freudenthal的原題中的人物當然不是鬼谷子、孫膑和龐涓，而且在數學意義上和我上面所說的也略有不同，其中規定兩個數必須不同，而且知道兩數和必定小于等于100（我們将要看到這其實并不使題目簡單多少）。 馬丁·加德納在1979年聽說了此題，将其發表在他著名的《科學美國人》數學專欄上，并稱其為“不可能問題”，因為這題看起來似乎缺少了一些條件，不可能解得出來。

所以現在這個問題被稱為“Freudenthal問題”，“不可能問題”或“和與積問題”。此篇文章中則稱其為“孫龐猜數問題”。題目裡被問到的人是孫膑和龐涓，或者更一般地說，是“非常聰明，推理迅速，邏輯無懈可擊，沒有絕對把握不會亂說話，隻說真話的人”，而且他們對此都清楚。這其實是一個不可或缺的條件，否則這題就真的不可能解了。在本文中談到的所有的題目中，我們都假設這個條件成立，不再強調。

二、比較簡單的題目

為了解釋孫龐猜數問題的解法，先解決一個此類問題中比較簡單的，也許是個好主意。

這類簡單問題往往猜的是撲克牌或生日。因為撲克牌有花色與點數兩個性質，知道花色點數則撲克牌确定；而生日則有月份與天号兩個性質，知道月份天号則生日确定。這同孫龐猜數問題中的兩個數有和與積兩個性質，知道兩數和與積，則兩數确定的情況是一樣的。（如果知道兩數和為S，積為P，那麼這兩數就是一元二次方程 x²-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給出的十個可能的生日日期按照月份和天号分類寫成一個交叉表：

表中有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月：

而Bernard聽了這句話，也能得出同樣的結論。不僅如此，他比我們還多知道一個天号，于是他說“現在我知道了”。這意味着，上面這張劃過的表，加上他所知的天号，就能得出Cheryl生日的唯一可能。所以Cheryl生日的天号不可能是14日，否則此時Bernard無法區别月份是7月還是8月。Bernard的這句話讓我們在已經劃過的表中，劃去所有那些其中有超過一個可能值的列。14日就是這樣一列：

Albert聽完Bernard的話後，也能得出同樣結論。不僅如此，他比我們還多知道一個月份号，于是他說“我也知道了”。這意味着，上面這張劃過的表，加上他所知的月份号，就能得出Cheryl生日的唯一可能。和上面Bernard說“知道了”類似，這讓我們在已經劃過的表中，劃去所有那些其中有超過一個可能值的行。8月是這樣的一行：

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

三、解法總結，孫龐猜數問題的算法解

通過上節的例子，看得出此類問題的解決方式很簡單。

1) 選定第一個說話的人知道的那個性質為行，另一人知道的性質為列，排出交叉表，并填入所有可能值。（哪個為行哪個為列當然無所謂，但如果選取的方式和這裡不同，下面的行/列說法也要反過來了。）

2) 劃去所有那些其中隻有一個值的行。（對應第一句說“我不知道”。）

3) 劃去所有那些列中隻有一個可能值時，那些值所在的行。（對應第一句說“我知道你不知道”。）

4) 劃去所有那些其中有超過一個可能值的列。（對應第二句說“我知道了”。）

5) 劃去所有那些其中有超過一個可能值的行。（對應第三句說“我知道了”。）表中剩下的值就是所有可能的解。

6) 如果隻剩下一個值，那麼我們（解題人）也知道了答案，解決了這個問題。

上面這個解法步驟對每一步需要做的事情的描述非常明确。事實上它描述了一種算法，很适合編個程序叫電腦來做。

于是用計算機程序很容易解決本文開頭的孫龐猜數問題。無非就是建一個200行（對應從1到200的兩數和值。雖然和值不可能是1，2或3，但是多設幾個空行并無所謂。列的情況類似），10000列（對應從1到10000的兩數積值）的交叉表劃上一通。對電腦來說處理這麼大小的表輕而易舉。

四、變化過的解法

但如果我們想用手算的方法來解決孫龐猜數問題，上面這個直接暴力的方法就不容易做了。所以這裡要将前面的解法變動一下。

回到Albert說完“我不知道Cheryl的生日是哪天，但是我知道Bernard也不知道。”這句話後我們得到的表格：

按照上面的算法，接下去根據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 2ⁿ*b。

這兩個樣子，其中a和b都是奇數，n>=1。那麼（當下面我說到“至少兩組數”中的兩組數都不相同，而且的确存在（也就是那些數都小于100）的理由我就不寫了，根據條件很顯然）：

或者孫膑的P=2*a*b，孫膑就會在(2*a,b)和(2,a*b)至少兩組數裡拿不定主意（a和b都是奇數，所以這兩組數一定不同）；

或者P=2ⁿ*a*b，

如果n>1，那麼孫膑就會在(2^n-1*a,2*b)和(2ⁿ*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=2ⁿ*p，其中n>1，p為奇素數的那些列是不會被劃去的。如果孫膑手裡有P=2ⁿ*p，他就知道唯一可能的數對是(2ⁿ,p)，因為除此之外，P的其他分解成兩數積的方式必定會是兩個偶數，而這些數對所在的行（和為偶數）都已經在前3步裡被劃去，不在表X裡了。所以列P中隻剩下(2ⁿ,p)這個數對，不會被劃去。

下面再舉不會被劃去的幾列，當然它們不是随便舉的，這幾列都會在下面被用到。

第2*3³=54列不會被劃去。因為它分解成兩數之積隻可能是(2,3³)=(2,27)，(2*3,3²)=(6,9)或(2*3²,3)=(18,3)，而後面兩個數對的和分别等于15和21，都不在集合C中，所以也不在表X中，孫膑可以排除。也即如果孫膑知道的兩數之積為54時，他就确定那兩數隻能是(2,27)，并說“我知道了”。

第2²*5²=100列不會被劃去。因為它分解成兩數之積隻可能是(2,2*5²)=(2,50)，(2²,5²)=(4,25)，(2²*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=2² 7=2³ 3，這是兩種把S拆成2ⁿ p，其中n>1，p為奇素數的方法。按照上面C)中的讨論，2²*7和2³*3這兩列都不會被劃去。所以S=11這行應被劃去。

類似地，

23=2² 19=2⁴ 7

27=2² 23=2⁴ 11

35=2² 31=2⁴ 19

37=2³ 29=2⁵ 5

47=2² 43=2⁴ 31

這些行都應被劃去。

于是S的可能值隻能在{17 29 41 53}中。讓我們繼續縮小這個表。

我們有29=2 27=4 25。根據C)中讨論，第2*27=54列和第4*25=100列都未被劃去，所以S=29應被劃去。

同樣41=2² 37=10 31。根據C)中讨論，第2²*37列和第10*31=310列都未被劃去，所以S=41應被劃去。

類似地53=2⁴ 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網站

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!