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

    考虑一个传统的猜数游戏。 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 可以询问任意多次。

Read more…

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

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

Read more…

2011年度最变态的迷宫难题

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

      

    你能成功走出来吗?

Read more…

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

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

      

    在 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

    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 的任务则是避免图形打结。

      

Read more…