在 2048 里能够得到的最大的数是多少?

Michael Brand 在 Using your Head is Permitted 趣题站 2014 年 4 月的谜题中提出了一个这样的问题:在最近非常流行的小游戏 2048 中,你能得到的最大的数是多少?

在这里,我们简单描述一下游戏的规则。游戏在一个 4 × 4 的棋盘上进行,棋盘里填有一个个的“数块”,每个数块上都写有某个形如 2n 的正整数。每一步,你需要从上、下、左、右四个方向中选取一个方向,按下对应的方向键之后,所有的数块都会“落”到这个方向;若有两个同种的数块在此过程中发生碰撞,则它们的值会相加起来,并合成一个新的数块。然后,系统会在棋盘中随机选择一个空白位置,并在此生出一个新的数块,上面写有数字 2 或者数字 4 (两种情况之比为 9 : 1)。游戏开始时,棋盘上会自动生成两个随机的数块,你的目标就是通过有限步的操作,得出一个写有 2048 的数块。当然,即使得到了 2048 这个数块,游戏也不会自动结束,你还可以向更大的数发起挑战。于是就有了我们刚才的问题:理论上,这个游戏当中能够得到的最大的数是多少?

Read more…

趣题:Kontsevich的单人跳棋游戏

      

    有一个无限大的棋盘,棋盘左下角有一个大小为 n 的阶梯形区域,其中最左下角的那个格子里有一枚棋子,如左图所示。你每次可以把一枚棋子“分裂”成两枚棋子,分别放在原位置的上边一格和右边一格。你的目的是通过有限次的操作,让整个阶梯里不再有任何棋子。下图所示的是 n = 2 时的一种解法。我们的问题是:对于那些 n ,这个游戏是有解的?

      

Read more…

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…