紫荆棘鸟：说说真是好玩那道逻辑推理题

送交者: 紫荆棘鸟 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)

	标 题 (必选项): 内 容 (选填项):

	实用资讯