Skip to content

Posts from the ‘Interesting Maths’ Category

12
Feb

“少数决”游戏

在SF神牛的鼎力推荐下看完了日剧《欺诈游戏》(Liar Game),大赞其游戏设计之强大,尤其是其中的“少数决”游戏。按照SF神牛的说法,看了这个日剧以后会觉得其他的博弈游戏都黯然失色...下面内容转载自http://www.matrix67.com/blog/archives/2591

欺诈游戏的第二场共有22人参加。这22个人集中在一个阴森的大厅里,参加一个叫做“少数决”的游戏。每一个游戏,从 Chinese PartyPoker 到象棋,都有它的规则。为了让游戏有意义规则必须被遵守,以便产生真正的胜者。当然,没有欺诈!游戏规则很有意思:主办方随机抽取一个人到台上来,向众人问一个二选一的问题,比如“你信春哥吗”。每个人手里都会得到两张选票,两张选票上都印有自己的名字,但其中一张纸上印有“YES”,另一张纸上印有“NO”。游戏者们有6个小时的时间进行交流和考虑,并要在时间结束前将自己的选择投入投票箱。时间结束后,主办方进行唱票,并规定票数较少的那一方取胜,多数派将全部被淘汰。获胜的选手将进行新一轮的游戏,主办方从剩下的人中重新选一位进行提问,并要求大家在6个小时内投票,唱票后仍然宣布少数派胜出。若某次投票后双方人数相等,则该轮游戏无效,继续下一轮。游戏一直进行下去,直到最后只剩下一人或两人为止(只剩两人时显然已无法分辨胜负)。所有被淘汰的人都必须缴纳罚金,这些罚金将作为奖金分给获胜者。

这个游戏有很多科学的地方,其中最有趣的地方就是,简单的结盟策略将变得彻底无效。如果游戏是多数人获胜,那你只要能成功说服其中11个人和你一起组队(并承诺最后将平分奖金),你们12个人便可以保证获胜。但在这里,票数少的那一方才算获胜,这个办法显然就不行了。因此,欺诈和诡辩将成为这个游戏中的最终手段。如果你是这22个参赛者中的其中一个,你会怎么做呢?…

1
Feb

一个与直觉相悖的概率问题及其引发的严肃思考

一人用颤抖的双手拿着艾滋病检测呈阳性的化验单去找医生:

“医生,弱弱的问一句,这个检测呈阳性是什么意思啊?”

医生:“同志,做好心理准备,你很有可能要悲剧了...目前艾滋病在世界上比较严重,粗略估计大概每1000人中就有一人得艾滋病。我们采用的是某种血液试验检测法用于检测身体中是否含有艾滋病病毒,这种方法相当精确,但也可能带来两种误诊。首先,他可能会让某些真有艾滋病的人得到阴性结果,称为假阴性,不过只有0.05的概率发生;其次,它还可能让某些没有艾滋病的人得到阳性结果,称为假阳性,不过只有0.01的概率会发生。根据这些数据,你差不多可以估计出来自己的囧况了...”

那人:“我X,哥悲剧了...”

OK虚拟的情境到此打住,我现在要问一个问题,请先不要计算,先尝试着用直觉给出一个答案:如果你就是这位哥,在艾滋病检检测呈阳性的条件下,你真的得了艾滋病的概率是多大呢?

请从下面ABC三个选项中选出与你的直觉最接近的:A.90%;  B.50%;  C.10%。…

5
Nov

Nim游戏的必胜策略和Xor运算的神奇应用

上一篇日志里介绍了Nim游戏,他的必胜策略可不是那么好想的。这个游戏貌似很久以前就已经有了,可是必胜策略直至20世纪初才被哈佛大学的一个叫做Charles Leonard Bouton的数学家找到,可见其思维难度;可是,这个必胜策略却只要由一个运算就搞定了:Xor(异或)运算,可见Xor运算之神奇。没有好好学过程序设计的人估计对Xor运算不甚熟悉,更不可能知道他的神奇应用了,因此我先说一说Xor运算。

Xor运算是位运算的一种,和And、Or运算类似,假如a、b都是布尔变量,则a Xor b被定义为:a、b相异则为真(所以中文名字叫做异或),a、b相同则为假。其真值表为:1Xor0=1, 0Xor1=1, 1Xor1=0, 0Xor0=0。众所周知,位运算也可以用于两个数之间,其定义就是把这两个数转化为二进制,然后一位一位的进行位运算。比如说1Xor4=(001)2 Xor(100)2=(101)2=5。位运算除了具有交换律、结合律这样的普通性质之外,还有几条神奇的性质。

Xor运算的神奇性质之一,就是他自己是自己的逆运算,即对于任何两个布尔变量或者数有(a Xor b)Xor b=a。这一点可以从真值表直接验证。有了这样一个性质,我们就可以把交换两个数的函数swap改进一下。大家应该都知道swap可以这么做:

void swap(int a, int b)

{a=a+b; b=a-b; a=a-b;} 

现在我们知道了Xor运算是本身的逆运算之后,就可以把上面的函数改成这个样子:(在C/C++里面把Xor表示为^)

void swap(int a, int b)

{a=a^b; b=a^b; a=a^b;}

乍一看肯定会觉得这个交换函数写的非常诡异,但是仔细一看就知道其原理和刚才那个是一模一样的。而且因为计算机在执行位运算的时候肯定比加减法要快,所以用Xor写的交换函数实际上还更快呢。

这里有一个有意思的小问题:现在给你2n+1个正整数,其中有n对数和1个单独的数,(这里规定一对数的意思是这两个数相等),然后让你设计一种算法,把这个单独的数给找出来,要求时间复杂度为O(n)。比如说这2n+1个数是1 2 …

21
Oct

拈游戏

所谓拈游戏的规则是这样的:(在看了沙发的评论之后我才知道其标准名字应该是Nim游戏...)

桌面上有三行硬币,每一行中分别有a1、a2、a3个硬币,其中a1、a2、a3是可以任意指定的正整数。两个人轮流拿走硬币,每一次只能从某一行中拿走任意多个硬币,谁拿走最后一枚硬币谁就赢了。

比如说a1=1,a2=2,a3=3的情况吧,这时如果轮到我拿了,我可以从第三行拿走2枚硬币,或者可以把第三行的三枚硬币全都拿走,等等;但是我不能同时从第一行和第三行里各拿走1枚硬币。这个简单的情况,可以枚举所有可能性得出结论:先拿的必输。

当a1、a2、a3是任意给定的,在什么情况下先拿的必输呢?必胜策略是怎样的呢?这是一个相当有意思的问题,答案可绝不是显而易见一目了然的。而当我当年看到这个策略长什么模样之后,完全的叹服了。今天我就先不写必胜策略了,大家可以先自己想想,如果下周或者什么时候有时间了再来写。前一阵子我为了熟悉C++自己写了一个拈游戏的人机对弈程序,大家可以点击下面的链接下载。其中包含了必胜策略,所以只要你一步走错就一定会输。

拈游戏.rar

其实拈游戏不仅仅局限于三行硬币,其实最初的问题是N行的,而且神奇的是其必胜策略对于任何N都是一样的。其实这个拈游戏是我上小学的时候奥数老师跟我玩的游戏,最近才发现这个经典的有意思的游戏还有好多人没有玩过,故写此文...…

20
Sep

猫捉老鼠问题

这个是我室友的力学老师留给他们的思考题,因为它完全符合思维过程相当困难、但是解答却极为漂亮简单的原则,所以我就转过来分享一下。

在数轴上,0的位置停着一个不动的老鼠,1的位置在初始时刻有一只猫。猫是可以走动的,每一步在数轴上分别以二分之一的概率或朝着正方向或朝着负方向走1的距离。当猫到达0的位置时,猫就抓到老鼠了,游戏结束。问当猫走的步数趋向于无穷大的时候,最终捉到老鼠的概率是多大?一定要先仔细思考再看解答...…

15
Sep

直上九宵的指数方程

有一道很简单的小问题:求解方程

这样的方程解起来是很简单的,因为最低下的x的指数是他本身,即它的指数是2,因此该方程等价于x^2=2,立刻解得x=√2。

但是,如果题目地形式稍微一变,变成这个样子:

用同样的方法你将会得出同样的答案x=√2。

现在问题来了,既然如此,那么表达式

到底等于几呢?2还是4?…