紫荊棘鳥：說說真是好玩那道邏輯推理題

送交者: 紫荊棘鳥 2013年03月28日15:37:11 於 [五 味 齋] 發送悄悄話

真是好玩同學那道題雖然只需要些加減乘除之類的計算，但是邏輯推理上是比較繞的。從這個意義而言，那道題算經典。原題表述很簡單，這裡拷貝如下： ------------------------------------------------ 一天，王先生拿出一套卡片，上寫從2到99個數字，每張一個數字。抽出兩張。相加之後，把和告訴張先生，把積告訴李先生。當然，張和李都不知道對方的數字是什麼。於是有如下一段對話：   張：我不知道那兩個數字是什麼，但是我知道你也不知道。   李：我本來不知道，你這麼一說我就知道了。   張：那我也知道了。   問：那兩個數字是什麼？ -------------------------------------------------- 原 題 post 出來後，有幾位同學例如捷克、胖子、實事求是等都試圖給個解答，但是似乎都沒有找到。這裡我也攙和幾句。不過，在進一步找到個簡單的方法求解前，具體計算 如果不能容易地找到，俺就免了 (目前我只有用手工一一去檢測或者費力寫個程序去計算這樣的笨辦法)，俺只就如何理解胡侃幾句。說得不對的地方請大家 (特別是帖主好玩同學) 指出。 鑑於原問題比較繞，我們先看個邏輯上相似但是推理上簡單不少的一個問題來幫助理解，但願詩人和藝術家都能看明白，呵呵。這個問題是在某個地方某人 post 出來的，大意是： --------------------------------------------------- 小明和小強都是張老師的學生，張老師的生日是M月N日，2人都知道張老師的生日是下列10組中的一天，張老師把M值告訴了小明，把N值告訴了小強，張老師問他們知道他的生日是那一天嗎？ 3月4日 3月5日 3月8日 6月4日 6月7日 9月1日 9月5日 12月1日 12月2日 12月8日 小明說：我不知道的，但是我也知道小強不知道。 小強說：本來我也不知道，但是現在我知道了。 小明說：哦，那我也知道了。 請根據以上對話推斷出張老師的生日是哪一天？ ------------------------------------------------------ 這 題比較直觀、簡單，例如這裡俺(大體上)抄襲捷克同學的解答，從第一句話可以得出不可能是 7 日 & 2 日，所以 7 月 & 12 月得排除，所以剩下的月份是 3 月 & 9 月；從第二句話可以判斷出，因為小強知道答案了，所以不可能是 5 日，因此候選答案只有 3月4日、3月8日、9月1日；從第三句話可以判斷出最終答案是 9 月 1 日。 好， 回到原題。先統一記號，假設這兩個數為 (a，b)，2 <= a < b <= 99，s = a + b，p = a*b。這樣張三得到的數字是 s，李四得到的數字是 p。(a，b) 總共有 98*97/2 = 4753 種組合。當然，像首尾兩頭的組合 (2、3)，(2，4) 以及 (97，99)、(98，99) 太 trivial，排除在外。 來 看第一句話。“ 張：我不知道那兩個數字是什麼，但是我知道你也不知道”，這句話意味什麼？這意味着 s (張三手中的數字) 不能表達為兩個素數的和，否則的話，例如如果 s = 8 = 3 + 5，李四手中的數 p 就可能是 15，而 15 只能分解成 3*5，從而能斷言這兩個數是 (3，5)。 因為 7 <= s <= 195 (除去首尾兩個特例)，所以 s 總共有189 種可能。我們將所有 s 構成的集合 S 分為兩個子集 S1、S2，其中 S1 是 S 中所有能表示為兩個素數之和的數的集合，S2 為剩餘的數的集合。顯然，從第一句對話，我們可以推斷出，a+b=s 不能在 S1 中，只能在 S2 中。鑑於小於 200 的素數大約有 200/ln200 = 38 個素數，根據哥德巴赫猜想，所有的偶數都能表示為兩個素數的和，而且 2 + all odd prime numbers 都是奇數，所以作為大體上的估算，S1 中大約有 95 + 38 = 133 個數，S2 中大約有 60 個數，所以從第一句對話中，我們就能去掉大約 2/3 的(a，b) 組合，可能的候選者大約只有 1500 種組合。當然，S 中有少數大偶數，例如 178 不一定能表示成兩個 100 以內的素數的和，但是這樣的數肯定很少，不影響大體上的估計。 再 考察第二句話：“我本來不知道，你這麼一說我就知道了”。李四手裡的數字是(a，b)  的乘積 p = a*b。假設將 p 分解成素數的乘積，p = p1^n1 * p2^n2 *...* pk^nk，其中 p1，...，pk 是素數，n1，...，nk >= 1，例如 90 = 2 * 3^2 * 5，這時 p 所對應的 (a，b) 組合，若不論 a、b < 100 這個約束，就有 n = (n1+1)*(n2+1)*...*(nk+1) / 2 -1 種可能的組合，例如對 90 而言，它可能的組合有 (1+1)(2+1)(1+1)/2 -1 = 5 種可能：90 = 2*45=3*30=5*18=6*15=9*10。現在李四能根據張三的第一句話能推斷出這兩個數是什麼，這意味着什麼？這意味着總共 n 種 (a, b) 組合中，他能恰好排除 (n-1) 種可能。或者等價地說，p 對應的 n 個 a+b，恰好有 (n-1) 個屬於集合 S1 中，1 個屬於 S2 中。我們看個具體的實例，p = 90，它能分解成 5 種可能的 a*b： p1)：90 = 2*45，2+45=47，屬於 S2 (因為們47 不能表示為兩個素數的和)； p2)：90 = 3*30，3+30=33 = 2+31，屬於 S1； p3)：90 = 5*18，5+18=23，屬於S2； p4)：90 = 6*15，6+15=21=2+19，屬於 S1； p5)：90 = 9*10，9+10=19=2+17，屬於 S1。 顯然，這裡 90 不滿足這個檢測，因為李四的這個數所有可能的分解中，除去那些越界的，必須恰好有且僅有一種分解，其和在集合S2中，這裡我們卻有兩個組合在 S2 中。 事事求是上次給的解答 (13，22) 也沒有通過第二步的檢測，因為 p = 13*22 = 2*143 = 11*26，除去 (2、143) 越界外，13+22 和 11+26 都不能表示為兩個素數的和，它們都屬於 S2。 再看另一例子：p = 52 = 4*13 = 2*26，4 + 13 屬於 S2，2+26 是偶數，屬於 S1，所以它能滿足第二步的檢測：(a，b) = (4，13)。當然 (4，13) 可能不滿足第三步的檢測。我們接下來考慮第三句話。 第 三句話是：“張(三)：那我也知道了”。注意張三手裡的數字是 s = a+b，通常，s 能表達為多種 a + b，例如 8 = 2 + 6 = 3 + 5，兩種；11 = 2+9=3+8=4+7=5+6，四種。一般，除去極端情形，s 不超過 100，s 能表示成 [ (s+1)/2] -2 種不同的 (a，b) 之和，這裡 [x] 表示 x 的整數部分。若 s 超過 100，那麼 s 就只能表示成總共 98 種表示 (考慮越界)。這句話的意思無非是說，張三看到手裡的 s 後，對所有可能的總共 min ([ (s+1)/2] -2，[ (197-s)/2])  種可能的 (a、b)，李四所對應的總共 min ([ (s+1)/2] -2，[ (197-s)/2]) 種可能的乘積 p，恰好存在一種組合使得李四能判斷出 (a，b)。亦即在這麼多不同的 p 中間，有且只有一個組合，滿足第一步和第二步的檢測。 很明顯，隨着 s 的增加，min ([ (s+1)/2] -2，[ (197-s)/2]) 也在增加 (然後變小)，要滿足第三個檢測 (亦即存在唯一一個組合使得李四能判斷) 也越來越困難。因此如果不依賴程序、只依賴手工去尋找這個組合，那麼先應該去從小 s 中尋找才能保證更高的機率。 具體看 s = 17。從上面的例子我們可以看出，(4、13) 是滿足前兩步檢測的。我們就以 s = 17 來看張三能否說“那我也知道了〃。我們有： s = 17 = 2+15=3+14=4+13=5+12=6+11=7+10=8+9 總共 7 種組合。 s1)：p=30=2*15=3*10=5*6，S1：3+10，S2：2+15，5+6；李四不能判斷； s2)：p=42=2*21=3*14=6*7，S1：6+7；S2：2+21，3+14；李四不能判斷； s3)：p=52=2*26=4*13，根據上面的討論，李四能判斷； s4)：p=60=2*30=3*20=4*15=5*12=6*10，其中3*20、5*12都屬於S2，所以李四不能判斷； s5)：p=66=2*33=3*22=6*11，其中2*33、6*11都屬於S2，所以李四不能判斷； s6)：p=70=2*35=5*14=7*10，其中2*35、7*10 都屬於S2，所以李四不能判斷； s7)：p=72=2*36=3*24=4*18=6*12=8*9，其中3*24、8*9 都屬於S2，所以李四不能判斷。 所以，對 s = 17，對所有可能的 7 種 a+b 組合，存在且唯一存在一種組合4+13，使得李四能判斷，以及張三能判斷。 所以，答案之一是 (4，13)。至於這答案是否唯一，靠手工計算，很很煩了。不過即使不唯一，滿足條件的答案估計也就那麼幾個，而且數字不會很大。

0%(0)

0%(0)

	標 題 (必選項): 內 容 (選填項):

	實用資訊