IMO2012趣题：带有说谎的猜数游戏

2012 年 7 月 22 日 / 33 条评论

考虑一个传统的猜数游戏。 A 、 B 两名玩家事先约定一个正整数 N ，然后 A 在心里想一个不超过 N 的正整数 x ， B 则需要通过向 A 提问来猜出 A 心里想的数。 B 的问题只有唯一的格式：先列出一些数，然后问 A “x 是否在这些数里”， A 则需要如实回答“是”或者“否”。显然， B 是保证能猜到 x 的，只需要依次询问“x 是否等于 1 ”，“x 是否等于 2 ”即可。由于 B 可以精心选出满足某种特征的所有数，询问 x 是否在这些数里，因而 B 还可以做得更好。例如当 N ＝ 16 时， B 第一次可以问“x 是否小于等于 8 ”，或者等价地，“x 是否属于 {1, 2, 3, 4, 5, 6, 7, 8} ”；接下来，根据 A 的回复继续细问“x 是否小于等于 4 ”或者“x 是否小于等于 12 ”，以此类推。另一种方法则是询问“x 的二进制表达的第一位是否是 1”，“x 的二进制表达的第二位是否是 1”，以此类推，从而获得 x 的二进制表达的所有数位，便能推出 x 来。

现在，有意思的问题来了。假设 A 可以偶尔说谎（但保证不会连续说谎两次），那么 B 还能通过询问猜出 A 所想的数吗？如果愿意的话， B 可以询问任意多次。

经典证明：星际争霸是NP-hard的

2012 年 1 月 28 日 / 55 条评论

今天看到这里给出了一个“星际争霸是 NP-hard 问题”的一个证明。具体地说，给定一个初始布局（包括地图、双方已有资源、双方已有建筑、双方已有兵力），判断其中一方是否能获胜，这个问题是 NP-hard 的。当然，考虑到即时战略游戏的复杂性，这个结论并不出人意料；真正有趣的，则是如何巧妙地利用游戏中的元素，构造出极其精巧的初始局面，从而转化成某个已知的 NP-complete 问题。下面是原文中给出的证明。这个证明有没有什么漏洞？你还能想到哪些别的证明方法？欢迎在下面留言一同分享。

2011年度最变态的迷宫难题

2011 年 11 月 30 日 / 82 条评论

下面大家将会看到的是一个极其简单而又极其复杂的“迷宫”，这无疑是我在本年度见到的最变态的谜题：从左边入口处的 2011 进去，在迷宫里转悠，最后变成 2012 从右边出来。你可以在迷宫里转圈，可以重复之前走过的路，但不能往回退着走。

你能成功走出来吗？

用生命游戏来模拟生命游戏

2011 年 11 月 14 日 / 32 条评论

这是我前几天看到的一个视频。毫无疑问，它是我所见过的各种生命游戏构造中最神奇的一个：

在 LifeWiki 中有一个词条详细介绍了这个构造：它叫做 OTCA metapixel ，是由 Brice Due 在 2005 至 2006 年间构造的。其中，每一个 metapixel 的大小为 2048 × 2048 ，周期为 35328 。

视频出处：http://www.youtube.com/watch?v=QtJ77qsLrpw
查看更多：http://www.reddit.com/r/math/comments/lutec/l_i_f_e_c_e_p_t_i_o_n_or_how_to_simulate_the/
如果你喜欢生命游戏，不要错过之前我们介绍过的史上最大的生命游戏构造—— Caterpillar 飞船

最难的组合游戏：To Knot or Not to Knot

2011 年 8 月 25 日 / 33 条评论

A Midsummer Knot’s Dream 简直可以说是去年学术界的一篇奇文，大家点进去看看就知道了。论文里讲了一个基于纽结理论的双人对弈游戏，名字也非常有艺术感： To Knot or Not to Knot 。这个游戏可能是最难的组合游戏了，它的数学性极强，思考难度非常大，甚至比 ERGO 更不容易上手。一场游戏下来，究竟谁赢谁输可能都不好判断。

To Knot or Not to Knot 的游戏规则非常简单。用铅笔在纸上画一个封闭的、可以自相交的回路，然后 A 、 B 两人轮流在图形中选取一个尚未被处理过的交叉点，并用橡皮擦对图形进行“细化”，明确两根线条的位置关系（可以抛掷硬币决定谁先行动）。A 的目的是要让最终的图形变成一个结，而 B 的目的则是避免图形打结。下面是其中一种可能的游戏过程，双方约定 B 先走。两人轮流对交叉点进行细化，七步之后，整个图形并未打结（你能看出来吗）， B 获得胜利。

注意，这是一个决策透明、信息公开的游戏，并且游戏不可能有平局产生。因此，即使双方都使出最佳策略，也必然有一个人会赢有一个人会输。也就是说，任意给定一个初始状态，总有一方有必胜的策略。不过，难就难在，究竟谁有必胜策略，必胜策略是什么，这并不容易判断。让我们来做一个练习题吧：下面的图形中，如果 A 先走，B 后走，谁有必胜策略？如果 B 先走，A 后走呢？记住，A 的任务是要让最终的图形打成结，而 B 的任务则是避免图形打结。