The Bottle Imp 是一则有意思的短篇小说。某日，小说里的主人公遇上了一个怪老头。怪老头拿出一个瓶子，说你可以买走这个瓶子，瓶子里的妖怪就能满足你的各种愿望；但同时，持有这个瓶子会让你死后入地狱永受炼狱之苦，唯一的解法就是把这个瓶子以一个更低的价格卖给别人。如果你是小说里的主人公，你会不会买下这个瓶子呢？你会以什么价格买下这个瓶子呢？
    以什么价格买入这个瓶子，这个问题貌似并不容易回答。你当然不愿意花太多的钱，在你的愿望被满足之前你至少还得给自己留一点钱花；但你也不能花太少的钱，否则你会承担着卖不出去的风险。但是，在做出一些理性的分析后，我们得出了一个惊人的结论：任何人都不应该以任何价格购买这个瓶子。
    和很多博弈问题一样，这一系列的分析首先从最简单的情形开始。首先，你是绝对不能只出 1 分钱就买下这个瓶子的，因为这样的话这个瓶子就永远也卖不出去了——没有比 1 分钱更低的金额了。那么，用 2 分钱买瓶子呢？这样理论上貌似是可行的，但仔细一推敲你会发现还是有问题——这样你只能以 1 分钱卖掉这个瓶子，但没有人会愿意用 1 分钱去买瓶子（否则他就卖不掉了）。因此，用 2 分钱买下瓶子后，你同样找不到下一个买家。和上面的推理一样，用 3 分钱买这个瓶子也不是什么好主意，因为没有人愿意以 1 分钱或 2 分钱购入瓶子，因此你的瓶子不可能卖得掉。依此类推，你不应该以任何价钱去购买这个瓶子，因为每个人都知道，他无法以任何价格卖掉这个瓶子。

查看更多 »

    前几天有网友推荐我看一部日剧叫做《欺诈游戏》，据说里面的高智商较量非常强大。最近这几天我看了前面几集，感觉和之前看过的一些推理日剧一样——剧情相当精彩，可惜拍得很烂。或许是不习惯日剧本身的画面风格吧。从第三集起，剧集进入了欺诈游戏第二场比赛之少数决游戏，有一段剧情相当科学。
    欺诈游戏的第二场共有22人参加。这22个人集中在一个阴森的大厅里，参加一个叫做“少数决”的游戏。游戏规则很有意思：主办方随机抽取一个人到台上来，向众人问一个二选一的问题，比如“你信春哥吗”。每个人手里都会得到两张选票，两张选票上都印有自己的名字，但其中一张纸上印有“YES”，另一张纸上印有“NO”。游戏者们有6个小时的时间进行交流和考虑，并要在时间结束前将自己的选择投入投票箱。时间结束后，主办方进行唱票，并规定票数较少的那一方取胜，多数派将全部被淘汰。获胜的选手将进行新一轮的游戏，主办方从剩下的人中重新选一位进行提问，并要求大家在6个小时内投票，唱票后仍然宣布少数派胜出。若某次投票后双方人数相等，则该轮游戏无效，继续下一轮。游戏一直进行下去，直到最后只剩下一人或两人为止（只剩两人时显然已无法分辨胜负）。所有被淘汰的人都必须缴纳罚金，这些罚金将作为奖金分给获胜者。
    这个游戏有很多科学的地方，其中最有趣的地方就是，简单的结盟策略将变得彻底无效。如果游戏是多数人获胜，那你只要能成功说服其中11个人和你一起组队（并承诺最后将平分奖金），你们12个人便可以保证获胜。但在这里，票数少的那一方才算获胜，这个办法显然就不行了。因此，欺诈和诡辩将成为这个游戏中的最终手段。如果你是这22个参赛者中的其中一个，你会怎么做呢？

查看更多 »

    故事发生在一个遥远的神秘世界。在那里，人们可以制造出不同等级的毒药。这种毒药是致命的，唯一的解药则是更强的毒药。若不幸中毒后，只要及时喝下更强的毒药就没事了，否则不管是谁都会在10分钟之内死亡。
    一天，恶魔向国王发起挑战，看谁拥有最毒的毒药。这是一场死亡竞赛，比赛规则很简单：双方各带一瓶毒药，先把对方瓶中的毒药喝掉一半，然后再把毒药换回来，把自己的毒药喝完。10分钟后，活下来的人便赢得这次比赛。恶魔藏有世上已知的最毒的毒药。国王知道，他无论如何也造不出比那更强的毒药来，并且也知道比赛时恶魔用的就是他那瓶绝无仅有的毒药。国王有办法赢得比赛吗？

    答案：国王有办法赢得比赛。在比赛开始前，国王先制造一个药性很弱的毒药，把它喝掉，然后拿着一瓶白开水去比赛。比赛时，国王喝掉恶魔手中的牛B毒药，反而没事了；恶魔喝的则是白开水。然后，国王喝掉自己的白开水，恶魔喝掉自己的牛B毒药；结果呢，即使他还想找解药都找不着了……因为他那瓶毒药已经是世上最牛B的了。

    不知道这个题目火星了没，反正今天我还是头一次见到。

查看更多 »

    去年的高中同学会上，吃完饭后大家就坐成一圈开始玩猜数游戏了。主持人自己在手机上输入一个1到，比如说500，的数，然后大家轮流猜数，并由主持人告之是猜大了还是猜小了。猜中了的那个人接受惩罚，真心话，或者大冒险，然后成为新的主持人。例如，我们班班长想了个数230。然后某男猜200，班长说“200到500”，意思就是200小了，以后的人只能猜200到500之间的数；接下来某女说“300”，美女班长说“200到300”；然后另一个MM猜250，班长回答“200到250”；然后就轮到我猜了，我说“230吧”，班长一脸坏笑把手机拿出来给大家看，说“哈哈，你猜中啦”。然后呢，我就和某个MM做了一件特别牛B的事情，细节呢就不在这里说了。
    当天同学会结束后我赶回学校机房继续讲课。我提出了这么一个问题：如果我不想猜中的话，怎么决策最好？如果我想猜中的话，又该猜什么呢？这个博弈过程复杂就复杂在，这是由多个人参与的游戏，目的不是尽早猜中或者最晚猜中，最佳决策很可能既不是猜正中间也不是猜最大或最小；游戏是一圈一圈地循环进行，策略要视总人数和数字范围而定，并且很可能每个人居心各不相同。

查看更多 »

    现在，我在心里想一个不超过n的正整数t。你的任务是尽可能用奇数次猜测猜中这个数（你知道n是多少）。每次猜测后，我都会告诉你你所做的猜测是大了还是小了。你不能猜测已经被排除了的数（来消耗猜测次数），你的每次猜测都必须符合我原来给出的回答。你觉得，你获胜（奇数次猜中）的几率有多大？

 
    动态规划的几个类似的经典模型启发了我们：设a[m]表示采取最优策略后在m个数里猜奇数次猜中的概率，b[m]表示如果题目要求我们猜偶数次，那最优策略下有m个数时获胜的概率是多少。考虑现在我有m个数可以猜，我想在奇数次内猜中。现在我猜的是数字i。狗屎运最好时，我一次猜中直接就赢了，它的概率是1/m；有(i-1)/m的情况下我会得到“大了”的提示，这样的话我需要用偶数次猜测去猜前面那i-1个数；剩余的那(m-i)/m的情况中，我需要用偶数次猜测去猜m-i个数。因此，a[m] = Max {1/m + (i-1)/m * b[i-1] + (m-i)/m * b[m-i], 1≤i≤m} 。类似地，我们也可以得出b[m]的递推公式：b[m] = Max {(i-1)/m * a[i-1] + (m-i)/m * a[m-i], 1≤i≤m} 。
    学习使用Mathematica确实是一件好事，你可以用Mathematica非常方便地描述出我们上面的两个递推公式，不需要自己去写那些冗长的程序了。
a[m_] := Max[Table[1/m + (i-1)/m * b[i-1] + (m-i)/m * b[m-i], {i, m}]]; a[0] := 0;
b[m_] := Max[Table[(i-1)/m * a[i-1] + (m-i)/m * a[m-i], {i, m}]]; b[0] := 0;

查看更多 »

    才知道，海盗分金问题有一个非常有趣的扩展。5个海盗分100个金块不难，100个海盗分100个金块也不难，事实上200个海盗分100个金块也不成问题。有趣的事情发生在第201个海盗身上——为了保命，他连一块金子都不能拿。他不得不把所有100块金子都分给前面199个人中奇数编号的人，从而贿赂他们投他的票（因为在第200个海盗的最优方案中这些人什么都得不到）。加上自己的一票共101票，过半了。同样地，第202个海盗也必须把100块金子分给在第201个海盗的方案中什么也得不到的人，贿赂他们投自己一票。由于第201个海盗的方案中有101个海盗得不到任何东西，因此他的方案不再唯一。加上自己的票共101票，正好是202的一半，这样一来他也活下来了。当问题扩展到N=203时，情况有了戏剧性的变化——第203个海盗无论如何都会死！因为只有100块金子，根本不够他用来贿赂，他无论如何也只能得到101票（别忘了题目条件假设海盗在自身利益相同的情况下会选择杀更多的人）。牛B就牛B在第204个海盗，虽然他也只能贿赂到100票，但是他居然活下来了！你猜他怎么活的？哈哈哈~~~~因为第203个海盗无论如何都会投他一票，不投他的话等轮到自己时就完了。因此第204个海盗把100个金子分给在第202个海盗的方案中啥也得不到的人，加上203和自己的票共102票，这才活了下来。类似地，你会发现第205个海盗必死；第206个海盗虽然会得到205的支持，但是票数仍然不够；207想活的话需要104票，但他也只能搞到103票；208将得到205、206、207的支持，加上自己的一票和贿赂来的100票，正好活了。以后，第216, 232, 264, …, 200+2^n个海盗都将活下来，游戏将在他们这里结束。

    考虑这样一个双人对弈游戏：在一个8x8的方阵里分别填上1-64这64个正整数。然后A和B两个人轮流在格子中取数，A先取，B后取。取数的规则很简单：取过的数不能够再取，并且除了第一次以外，以后每次取的数必须与某个已经取过的格子相邻。所有数都取完后，所取数之和最大的人获胜。
    很显然，这个游戏对于A更有利一些。我们可以轻易构造一个初始状态，使得先取的人必胜。考虑A的这样一个策略：总是取能取的数中最大的一个。如果每次A都可以取走整个棋盘中最大的那个数，那A就赢定了（因为每次B接下来取的数都比A小）。这样的初始状态是很容易构造出来的，比如我们只需要从左往右从上至下依次填入这64个数就可以了，这可以保证如果从n到64的所有数都取走了，则n-1也可以被取走。
    现在的问题是，能否构造一个初始状态，使得后取的人有必胜策略？提示，解决这道题需要有超强的“整人”能力。你得想出足够多的坏点子才能找到弄死先行者的方法。你的心肠坏到足以解决这个问题吗？



































  
    解决问题的关键在于，我们要给A埋下“陷阱”。考虑这样一种局部构造：奇数个大数彼此相连，这些大数周围一圈全是小数。上图就是这样一个陷阱，钻石代表大数，其余黄色的格子都是小数。只要A踩进了某个黄色格子，他就中计了：B和A开始轮流取大数，但大数只有奇数个，因此B获得的大数比A多一个。为了让事情变得更简单，我们只考虑最简单的一种陷阱：只有一个大数，周围的邻格都是小数。我们还有几个难点：万一A一开始就把陷阱内的钻石取走咋办，又如何避免自己不会掉进陷阱，还有我们必须保证B从这些陷阱里赚到的足以弥补在其它地方亏的。要想有足够多的陷阱对A起作用，我们得布上至少三个陷阱，这样A可以在最能赚的陷阱里开局，但无法避免落入另外两个陷阱。为了保证自己不会掉进陷阱，我们可以把棋盘的其余部分划分为多米诺骨牌（一个个1x2的小长方形），这样的话不管A取哪一个格子，B总可以取对应的另一个格子，不会踩到陷阱。于是我们想到了下面的这个构造：

    

    我们在四个陷阱里分别填上1-2-3-61，4-5-6-62，7-8-9-63，10-11-12-64这四组数，每个多米诺骨牌里填上两个相邻的数。这样的话，A的最好策略就是从第一个陷阱里开始取数。他能从第一个陷阱里赚到(61+2)-(1+3)=59分，但他在其它陷阱里将分别丢掉(62+4)-(5+6)=55分、(63+7)-(8+9)=53分、(64+10)-(11+12)=51分。而多米诺骨牌一共只有24个，他最多只能捡24分回来，这是远远不够的。因此，先取者必输无疑。

参考资料：http://www.brand.site.co.il/riddles/200802q.html

  
    有这样的一类组合游戏，对于任一个游戏局面，游戏双方的合法决策都完全一样，游戏对战双方的唯一区别就是看谁先走。这样的游戏叫做Impartial Games。像什么报数啊，取火柴啊，取石子啊，这些游戏都属于Impartial Games；而象棋、围棋等要分棋子颜色的游戏则不属于Impartial Games。共享状态的游戏几乎没有可玩性，因为游戏开始前我们就能知道谁赢谁输（如果双方均使用最佳策略）。棋局的任一状态只有两种，面对这个棋局的人要么必胜要么必败。考虑这样的一个递推关系：如果一个状态是必胜态，那至少有一种走法能走成一个必败态留给对方；如果一个状态是必败态，那它怎么走都只能走到必胜态。运用这样的关系，我们可以自底向上推出初始状态是必胜还是必败。
    近来有人提出一个名为Atropos的游戏，它就是一个即使计算机也很难办的Impartial Game，它能保证这个游戏仍然具有可玩性。游戏在一个Sperner三角形上进行，上图就是一个边长为7的Sperner三角形。游戏开始后，双方依次在白色的圆圈里涂上红色、绿色或者蓝色，已经涂过颜色的圆圈不能再涂色。另外，只要有可能，所涂的圆圈都必须紧挨着上次对方涂的那个圆圈。谁先涂出三种颜色都有的小三角形，谁就输掉这场游戏。

  
    注意这个游戏是不可能出现平局的。当所有白色圆圈全部涂上了颜色后，至少会出现一个红绿蓝小三角形。为了证明这一点，我们可以在所有的绿色和红色圆圈中间画一个箭头，红的在箭头右边，绿的在箭头左边。这些箭头一定组成了一条一条的路径，它们既不会交汇也不会分岔。但整个图的边界上进来的箭头有4个，出去的箭头只有3个，于是至少有一条路径在里面走死了，也即迎面碰上了蓝色的圆圈。这样，我们就找到了一个红绿蓝三色都有的小三角形。

    这个游戏虽然属于Impartial Games，但它仍然具有可玩性。从直觉上看，这个游戏中的先手后手几乎没有区别，谁也不占优势。这篇论文则严格证明了，判断Atropos游戏的最佳策略属于PSPACE-complete，这是所有使用多项式空间的问题中最难的一类，所有使用多项式空间的问题都可以（在多项式的时间内）约化到它。这说明，Atropos游戏没有什么很显然的“决窍”，即使利用计算机也很难确定最优决策。

在线游戏：http://cs-people.bu.edu/paithan/spernerGame/SpernerGame.html (Java Applet)
查看更多：http://cs-people.bu.edu/paithan/spernerGame/