2011年10月16日星期日

Fwd: 分析笑话:数学系有三个班

“数学系有三个班”是真的,可我从来没听过这样有趣的对话:
先分析一下原版的吧,说来惭愧,还是老婆给我讲明白的呢。

数学系一共3个班。
男生:你是3班的么?
女生:原来你是2班的啊!
男生:你是1班的啊!


初始:
男生知道自己是2班的,男生知道女生不是自己班的,所以男生知道女生是1班或3班的
女生知道自己是1班的,女生知道男生不是自己班的,所以女生知道男生是2班或3班的
第一句话:
男生问女生是不是3班的,相当于宣布自己不是3班的,因为如果男生是3班的,他就不用问这个问题了。这里假设这两个人认识自己班的所有人,并且彼此知道这一点。
所以女生知道男生是2班的了。
第二句话:
女生说“原来你是2班的啊”,相当于宣布自己之前不知道男生是2班的,现在得到足够的信息知道了。
第三句话:
男生是如何推断出女生是1班的呢?
假设女生是3班的,那么女生只能知道男生是1班或2班的。那么男生告诉女生自己不是3班的并没有给女生提供任何新的信息。那样的话,女生就不足以推断出男生是2班的。这和第二句话不符。
所以女生只能是1班的。



趁老婆还在玩iCloud没去睡,再分析一个鬼谷子版的吧

一天,鬼谷子随意从2-99中选取了两个数。他把这两个数的和告诉了庞涓, 把这两个数
的乘积告诉了孙膑。但孙膑和庞涓彼此不知到对方得到的数。第二天, 庞涓很有自信的
对孙膑说:虽然我不知到这两个数是什麽,但我知道你一定也不知 道。随后,孙膑说:
那我知道了。庞涓说:那我也知道了。

这其实就是YaoQiZhi老师课上讲的Mr. S & Mr. M的故事,当时觉得好难啊,现在学了点python,觉得暴力破解法很直接,code也不过一屏。


from itertools import product
from collections import defaultdict
n=552
a0 = set([p for p in product(range(2,n), range(2,n)) if p[0]<p[1]])
print len(a0)
s=defaultdict(set)
m=defaultdict(set)
for (x,y) in a0:
        s[x+y].add((x,y))
        m[x*y].add((x,y))
print len(s)
print len(m)
#I don't know, you don't know
a2=set([(x,y) for (x,y) in a0 if len(s[x+y])>=2 and len(m[x*y])>=2])
print len(a2)
#I know you don't know
a3=set([(x,y) for (x,y) in a2 if all([len(m[p*q])>=2 for (p,q) in s[x+y]])])
print len(a3)
#you know
a4=set([(x,y) for (x,y) in a3 if len(a3 & m[x*y])==1])
print len(a4)
#I know
a5=set([(x,y) for (x,y) in a4 if len(a4 & s[x+y])==1])
print a5


ytwang$ time python v.py
150975
1097
77432
105205
4753
2058
set([(4, 13)])

real     0m18.002s
user     0m17.919s
sys     0m0.079s



计算复杂度的瓶颈在求a3,也就是“我知道你不知道”这句话蕴含了绝大多数信息量。




没有评论: