UyHiP-Apr-2014

2048 已经打入敌人内部了是吗……

Problem

给定一种奇怪规则的 2048 ，问可能凑出来的最大的数是多少。

规则比普通的 2048 多了一条：如果这次合并后还可以继续合并，那么就不会出现新的方块。

注意每次可以出现 2 或 4 。

Solution

其实 yy 一下就可以猜出答案是 \(2^{17}\) 。

怎么解释呢……一开始我的想法是在一个局面中出现两个相同的数是不优的，可是怎么证明是不优的呢。我觉得这显然，但是 Michael 说要给理由，于是我就没继续想下去了。

后来脑洞大开，yy 了另外一个思路。就是考虑整个局面中所有元素的和。每次这个和要么增加 2 要么增加 4 。注意到这个和的二进制表示中 1 的个数的意义，1 的个数表示这个局面中最少要多少个方块。如果要产生一个 \(2^{18}\) ，那么一定存在一个时刻使得整个和要么为 \(2^{18} - 2\) 要么为 \(2^{18} - 4\) 。注意到显然不能为 \(2^{18} - 2\) ，因为 \(2^{18} - 2\) 有 17 个 1，而 \(2^{18} - 4\) 里面有 16 个 1，已经把棋盘塞满了，游戏已结束，也是不可能的。所以 \(2^{18}\) 是不可能出来的。

这样的话就只要考虑 \(2^{17}\) 了。显然这是可能的，很容易构造的吧……