“少数决”游戏

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

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

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

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)₂ Xor(100)₂=(101)₂=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 …

两个好玩的数学游戏

这两个数学游戏，为佘飞所发明，个人认为相当有意思，我们玩儿了好长时间了，作为无聊繁重的课业之余的休闲娱乐活动。

1. 两人轮流从1～20中写数字，谁写下的数字中有4个之和为40谁就是赢家。写数字的时候每一轮都是分别写好然后再同时亮出来，已经写过的数字以后不可以再重复写。如果出现某一轮两人写的数各自可以凑成和为40，则这一轮两人写下的数字被划掉，而且以后也不准再写这个数。如果某一轮两人写了同一个数字，其中甲可以用它凑出40，而乙不行，则甲的那个数就被划掉，而乙的则保留下来。如果某一轮两人写了9同一个数字而且都无法用其凑出40，则同时被保留。

下面是一次游戏作为例子：…

几道有意思的小数学题

1.“一切无理数的无理数次方一定是无理数”，试证明此命题或举出反例。

2.两人在1，2，3，……，9这九个数字中轮流取数，不准重复，谁先取到三数之和为15谁就赢了。问先走者有没有一个稳操胜券的策略？

3.汽油危机已经来临，大家都在叫油荒。分散在长长的环形公路各处的加油站所存的油量仅仅够你跑一圈而无点滴富余。请证明，如果你在一个合适的加油站开始启程，把空油箱加足了汽油，你有充分把握可以跑完一圈，不会中途抛锚。

请先仔细思考再看解答.

 …