说说真是好玩那道逻辑推理题-紫荆棘鸟-万维博客-万维读者网（电脑版）

设万维读者为首页

万维读者网 -- 全球华人的精神家园

广告服务

联系我们

关于万维

首　页

新　闻

视　频

博　客

论　坛

分类广告

购　物




--紫色王家思絮絮--
我思无邪、我行无悔
		https://blog.creaders.net/u/1639/ > 复制 > 收藏本页

网络日志正文

		说说真是好玩那道逻辑推理题	2013-03-28 15:37:11


	真是好玩同学那道题虽然只需要些加减乘除之类的计算，但是逻辑推理上是比较绕的。从这个意义而言，那道题算经典。原题表述很简单，这里拷贝如下： ------------------------------------------------ 一天，王先生拿出一套卡片，上写从 2 到 99，共 98 个数，每张一个数字。抽出两张。相加之后，把和告诉张先生，把积告诉李先生。当然，张和李都不知道对方的数字是什么。于是有如下一段对话：张：我不知道那两个数字是什么，但是我知道你也不知道。李：我本来不知道，你这么一说我就知道了。张：那我也知道了。问：那两个数字是什么？ -------------------------------------------------- 原题 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 = ab。这样张三得到的数字是 s，李四得到的数字是 p。(a，b) 总共有 9897/2 = 4753 种组合。当然，像首尾两头的组合 (2、3)，(2，4) 以及 (97，99)、(98，99) 太 trivial，排除在外。来看第一句话。“ 张：我不知道那两个数字是什么，但是我知道你也不知道”，这句话意味什么？这意味着 s (张三手中的数字) 不能表达为两个素数的和，否则的话，例如如果 s = 8 = 3 + 5，李四手中的数 p 就可能是 15，而 15 只能分解成 35，从而能断言这两个数是 (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 = ab。假设将 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 = 245=330=518=615=910。现在李四能根据张三的第一句话能推断出这两个数是什么，这意味着什么？这意味着总共 n 种 (a, b) 组合中，他能恰好排除 (n-1) 种可能。或者等价地说，p 对应的 n 个 a+b，恰好有 (n-1) 个属于集合 S1 中，1 个属于 S2 中。我们看个具体的实例，p = 90，它能分解成 5 种可能的 ab： p1)：90 = 245，2+45=47，属于 S2 (因为们47 不能表示为两个素数的和)； p2)：90 = 330，3+30=33 = 2+31，属于 S1； p3)：90 = 518，5+18=23，属于S2； p4)：90 = 615，6+15=21=2+19，属于 S1； p5)：90 = 910，9+10=19=2+17，属于 S1。显然，这里 90 不满足这个检测，因为李四的这个数所有可能的分解中，除去那些越界的，必须恰好有且仅有一种分解，其和在集合S2中，这里我们却有两个组合在 S2 中。事事求是上次给的解答 (13，22) 也没有通过第二步的检测，因为 p = 1322 = 2143 = 1126，除去 (2、143) 越界外，13+22 和 11+26 都不能表示为两个素数的和，它们都属于 S2。再看另一例子：p = 52 = 413 = 226，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=215=310=56，S1：3+10，S2：2+15，5+6；李四不能判断； s2)：p=42=221=314=67，S1：6+7；S2：2+21，3+14；李四不能判断； s3)：p=52=226=413，根据上面的讨论，李四能判断； s4)：p=60=230=320=415=512=610，其中320、512都属于S2，所以李四不能判断； s5)：p=66=233=322=611，其中233、611都属于S2，所以李四不能判断； s6)：p=70=235=514=710，其中235、710 都属于S2，所以李四不能判断； s7)：p=72=236=324=418=612=89，其中324、8*9 都属于S2，所以李四不能判断。所以，对 s = 17，对所有可能的 7 种 a+b 组合，存在且唯一存在一种组合4+13，使得李四能判断，以及张三能判断。所以，答案之一是 (4，13)。至于这答案是否唯一，靠手工计算，很很烦了。不过即使不唯一，满足条件的答案估计也就那么几个，而且数字不会很大。

浏览(4472)

(0)

发表评论


			文章评论

作者：紫荆棘鸟

留言时间：2013-04-11 13:02:35

thread 的程序有错误。事实上，当 N 很大时，解不会唯一。
当 N < 400 时，解还是唯一的，但是到了 500，就有 2 个解答：
(4，13) and (4, 61)


	回复 \| 0 评论前需要先登录或者注册哦发表

作者：紫荆棘鸟

留言时间：2013-04-01 07:46:44

谢。thread 同学编了个程序，见楼上的拷贝 (不过程序贴后可能被网站的 PHP 吃了什么符号，例如小于号之类)，说是若将卡片数增加到 999 (from 99)，(3、14) 也是唯一的一个解。这多少出乎我的意料。我最开始的直观估计是，答案尽管会很少 (因为约束太多)，但是可能不会唯一。


	回复 \| 0 评论前需要先登录或者注册哦发表

作者：嘎拉哈

留言时间：2013-03-31 14:11:33

俺对第一句就理解错了。俺以为，从第二句看，似乎第一句的 “但我知道你也不知道”是句废话。其实这句话至关重要。

1. S 不属于 S1，并且 S 的所有可能组合数之积都不属于 P1。

比如：

S=8=2+6=3+5 属于S2. 虽然2*6=12=2*6=3*4 属于 P2,但是 3×15=15 却属于P1. 因而违反了“但我知道你也不知道”这句话。


	回复 \| 0 评论前需要先登录或者注册哦发表

作者：紫荆棘鸟

留言时间：2013-03-30 13:36:53

送交者: thread 2013月03月30日13:04:56

#include "stdafx.h"
#include "memory.h"

struct Pair
{
int a, b, s, p;
int f; // filter mark
};

#define MAX_NUMBER 99 //999

const int nListSize = (MAX_NUMBER-1)*(MAX_NUMBER-2)/2;

Pair l[nListSize];

void Init()
{
int i = 0;
for (int a=2; a<MAX_NUMBER; a++) {
for (int b=a+1; b<=MAX_NUMBER; b++) {
l.a = a;
l.b = b;
l.s = a+b;
l.p = a*b;
l[i++].f = 0;
}
}
printf("Init %d == %d ", nListSize, i);

}

int GetCount()
{
int nCount = 0;
for (int i=0; i<nListSize; i++) {
if (l.f == 0) {
nCount++;
}
}
return nCount;
}

const int sMarkSize = 2*MAX_NUMBER;
const int pMarkSize = MAX_NUMBER*MAX_NUMBER;
int sMark[sMarkSize];
int pMark[pMarkSize];
void Filter1()
{
int nCount0 = GetCount();

memset(sMark, 0, sMarkSize*sizeof(int));
memset(pMark, 0, pMarkSize*sizeof(int));

for (int i=0; i<nListSize; i++) {
sMark[l.s]++;
pMark[l.p]++;
}

int f1 = 0;
int f2 = 0;
int f3 = 0;
for (int i=0; i<nListSize; i++) {
if (sMark[l.s] == 1) {
l.f |= 1;
f1++;
}
if (pMark[l.p] == 1) {
l.f |= 2;
int s = l.s;
for (int j=0; j<nListSize; j++) {
if (l[j].s == s && l[j].f == 0) {
l[j].f |= 4;
f3++;
}
}
f2++;
}
}

int nCount1 = GetCount();
printf("Filter1 %d => %d (%d+%d+%d) = %d ", nCount0, nCount1, f1, f2, f3, f1+f2+f3);
}

void Filter2()
{
int nCount0 = GetCount();

memset(pMark, 0, pMarkSize*sizeof(int));

for (int i=0; i<nListSize; i++) {
if (l.f == 0) {
int p = l.p;
pMark[p]++;
}
}

int fc = 0;
for (int i=0; i<nListSize; i++) {
if (l.f == 0) {
int p = l.p;
if (pMark[p] != 1 && pMark[p] != 0) {
l.f |= 8;
fc++;
}
}
}

int nCount1 = GetCount();
printf("Filter2 %d => %d (%d) ", nCount0, nCount1, fc);
}

void Filter3()
{
int nCount0 = GetCount();

memset(sMark, 0, sMarkSize*sizeof(int));

for (int i=0; i<nListSize; i++) {
if (l.f == 0) {
sMark[l.s]++;
}
}

int fc = 0;
for (int i=0; i<nListSize; i++) {
if (l.f == 0) {
if (sMark[l.s] != 1 && sMark[l.s] != 0) {
l.f |= 0x10;
fc++;
}
}
}

int nCount1 = GetCount();
printf("Filter3 %d => %d (%d) ", nCount0, nCount1, fc);
}

void Print()
{
printf(" Print Result: ");
int c=0;
for (int i=0; i<nListSize; i++) {
if (l.f == 0) {
printf("[%d] (%d,%d) s=%d, p=%d ", ++c, l.a, l.b, l.s, l.p);
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
Init();
Filter1();
Filter2();
Filter3();

Print();

return 0;
}

/*
#define MAX_NUMBER 999

Init 497503 == 497503
Filter1 497503 => 16711 (4+144416+478930) = 623350
Filter2 16711 => 6341 (10370)
Filter3 6341 => 1 (6340)

Print Result:
[1] (4,13) s=17, p=52
*/

/*
Init 4753 == 4753
Filter1 4753 => 145 (4+1732+4425) = 6161
Filter2 145 => 86 (59)
Filter3 86 => 1 (85)

Print Result:
[1] (4,13) s=17, p=52
*/


	回复 \| 0 评论前需要先登录或者注册哦发表

作者：紫荆棘鸟

留言时间：2013-03-29 08:26:43

能否表示为两个素数的乘积，是整个题的取舍标准啊，像第二句话、第三句话，无非就是围绕这个标准对可能的组合“抽丝剥茧”而已。
此题不难，但是很烦很繁，根源就在素数分布的无规律性。


	回复 \| 0 评论前需要先登录或者注册哦发表

作者：嘎拉哈

留言时间：2013-03-29 08:04:54

假定上面的逻辑是正确的。那末问题就变得容易多了。和要比乘积容易些。

S2 里面只有四个元素： S2=(7,8,194,195)

7=2+5=3+4
8=3+5=2+6
194=96+98=95+99
195=97+98=96+99

接下来，只要在 P2 的所有中找到如下8个数之一即可：

2x5=10
3x4=12
3x5=15
2x6=12
96x98=9408
95x99=9405
97x98=9506
96x99=9504


	回复 \| 0 评论前需要先登录或者注册哦发表

作者：嘎拉哈

留言时间：2013-03-29 07:19:09

回鸟儿：

俺还没有来得及仔细读你的推导。但俺猜测您应当和俺不约而同地使用 S1，S2，P1, P2 来定义同样的子集。但事实上不是这样。

在俺这里，Si 表示由所有 i 种可能组合的二数之和所构成的子集。以原题为例，5=2+3 属于 S1, 7=2+5=3+4 属于S2， 9=2+7=3+6=4+5 属于 S3.

俺至今没明白为什需要素数的概念。俺感觉好像不需要。

其实可以把第一和第三条捏在一起，此问题的最终逻辑关系可以表达为：

1. P 属于 P2， if S 不属于 S1 then P=a*b, otherwise P=c*d;
2. S 属于 S2， if P 属于 P2 then S=a+b, otherwise S=c+d;

下一步就是把 S 和 P 的所有可能组合表为 S1,S2,S3 。。。。 P1,P2,P3 。。。。。。


	回复 \| 0 评论前需要先登录或者注册哦发表

作者：紫荆棘鸟

留言时间：2013-03-29 06:22:39

谢。打符号很麻烦是吧？那个属于不属于用括号代替，看得一愣一愣的...
P1、P2是啥？


	回复 \| 0 评论前需要先登录或者注册哦发表

作者：嘎拉哈

留言时间：2013-03-29 06:13:55

改正第二条：

2. 根据李： P（P2, 并且 if S （ S1 then P= P2,1，otherwise P=P2,2 。由于张说 S!( S1，因此李断定 P = P2,2。


	回复 \| 0 评论前需要先登录或者注册哦发表

作者：嘎拉哈

留言时间：2013-03-29 04:28:50

这个题目确实很好玩。可以作为逻辑练习题。俺的思路和你的大体一样。

假定两个数为A 和 B。 A+B=S & AB=P。

使用如下符号约定：

！= 不等于
( 属于。
！（不属于。

1. 根据张： S ！（ S1 并且 P ！（ P1;

2. 根据李： P（P2, 并且其中之一 P2，1 （ S1 和另外一个 P2,2 （ S2。由于张说 S!( S1，因此李断定 S （ S2, 所以 P = P2,2。

3. 根据张：S=S2，if P( P2 then S=S2,1 otherwise S=S2,2。由于李说 P （ P2.因此张断定 S=S2,2。

不保证正确。

（待续）