0%

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}\) 了。显然这是可能的,很容易构造的吧……