游戏快报

极客向:2048这个游戏,最多可以累积到多大?

极客向:2048这个游戏,最多可以累积到多大?

这是来自果壳问答的内容,看看技术帝们如何玩游戏。

Q:最近在玩2048那个游戏

玩顺了以后,2048还是能够比较轻松地达到的,但是再高呢?有没有人可以证明,4096是无法实现的?

鉴于楼里面有人提出4096已有百分百的通关方式,8192也有人成功过。还有人提出,最大可能是131072……但是楼主自己猜,要实现这个131072,运气的成分可能更大一点。

所以想修改一下问题:求问,能够给出必胜策略的最大值是多少??

@蜡笔桶拉出来溜溜

更多因为新出的是2或者4

因此,在脸最好的情况下

16个格子最多可以合出2^17=131072

这个事情是这样的

为了合出一个2^(N+1)

你必须有两个2^N

而且必须先合出第一个,再合出第二个

呃,虽然上面这句看似有些废话,但重点在于,你合第二个2^N的时候,由于第一个2^N的存在,会占用格子数

同理,为了合出第二个2^N,你得在【存在一个2^N,且存在一个2^(N-1)】的情况下,合出第二个2^(N-1)

因此,“最多能合出多少”这个问题,可以转化为“最多可以有多少格子被占用”

于是,16个格子,前15个被所有那些“第一个2^n”占用之后,剩下刷出一个4,这就是最极端的情况

此时场上最大的数是2^16=65536,把它们全合起来就得到131072

@南方的星星0218

楼上@蜡笔桶拉出来溜溜
的答案太理想化了,显然是不对的。要想达到2的17次方,场上唯一可能的排列方式一串2的n次的等比数列串成一串,并且,最后要刷出4还得是制定的排列方式,比如:

65536|512 |256|4

32768|1024|128|空

16384|2048|64 |8

8192 |4096|32 |16

而要想达成这种排列,上一步的最右一列从上到下必须是4 4 8
8,然而,这一排列的再上一步无论如何都推不出来了。所以,继续求解,求高级一点的解法。

@Nauden

必胜策略的最大值应该就是2048。

摘要:

先写一下证明思路吧:

一,当随机生成的数是2或4时,能确保生成的最大数是4,且能够在任意位置生成(①这个数不大于4,②这个数不小于4,③4可以在任意位置生成)。

二,当一行能在任意位置生成n时,则可以在相邻行的任意位置生成2n。

三,当一行以n为单位进行有计划的合成时,能确保生成的最大数是4n,且能在任意位置生成。(①这个数不大于4n,②这个数不小于4n,③4n可以在任意位置生成)。

4X2(4X2(4X2(4)))=2048。

一,

证明:

先证这个数最大是4。

只要举出一个不能生成8的反例就够了:出现一个2,移向一侧,紧邻着2出现一个4,此时只能移向另一侧,2的另一侧出现一个4,此时又只能移回来,出现一个2。变成4242,扑街。

(这个连续出现两个4比较少见,但是可能存在,在我们现在讨论的问题中,就是要讨论”最坏“的运气,而且4242这种悲剧大家应该都遇到过吧。)

再证这个数至少是4。

反证法,如果这一行没有4,那么剩下的全是2或0,游戏不可能结束。

于是我们证明了这个数是4。

但是光生成4是不够的,比如我们要在右边累加数字,结果出现了4242,还是一样要扑街的,所

以我们要进一步讨论:能否在指定位置生成4?答案是肯定的。

证明:

由于2和4组成的行游戏结束的必须条件是形成“4242”和“2424”,我们只要证明指定位置4的生成不晚于这样的情况的出现就可以了,由于这两种情况是完全对称的,所以下面我们只就4242进行证明。

4242的上一步只能是以下几种情况:

①0424 ②4024 ③4204 ④2420 ⑤2402 ⑥2042 ⑦2224

要使4出现在

第一格:①⑦:左移;②③:不动;④⑤⑥:右移–2242则左移;4242则不动

第二格:①④⑤:不动;②③:右移;⑥:左移;⑦:右移–4244则右移;2244则左移再右移。

第三格:①②③⑦:左移;④⑤:右移;⑥:不动

第四格:①②③⑦:不动;⑤⑥:左移–2424则不动,2422则右移;④:无解。

这里发现2420的情况是不能够保证在第四个生成4的,所以我们针对这种情况再往前推一步,由于这里的4在中间,不可能是加和生成的,于是242的上一步只可能是0024,0204,2004,2040中的一种,此时只要进行右移或者不动就可以在第四格得到一个4。

至此,我们已经证明了可以在第四行的任意位置得到一个4。

二,

当我们可以在最下一行任意位置生成4的时候,必然可以在整个16宫格的任意位置生成4或比4更大的数,于是我们可以确保整个十六宫格上三行的数至少是4。由于在最下一行的指定位置可以生成4,所以对于倒数第二行出现的任意一个4,都可以补足,生成8,于是倒数第二行可以视作一个以8为最小单位的行。

三,

下面我们不禁会想?如果2为单位能保证生成4,那么8为单位,能保证生成的最大数是不是16呢?答案是否定的。

因为对于最后一行而言,4是可能凭空出现的,而在倒数第二行中,16确是不会凭空出现的。于是我们下面来探究倒数第二行能够获得的最大数字。

把问题简化为,新生成的数只有2时,最后一行能获得的最大数字是多少呢?答案是8

证明:

先证这个数最大是8。

举一个反例:2000,左移–2002,左移(很显然这里左移右移是没有区别的,不需要考虑最优方案的问题–这句话下文中都用*号表示),4200,只能右移–0242,只能左移–2422

①左移–2442,左移(*),2822,右移(左移就2842扑街了)–2284,只能左移–4842,扑街。

②右移–2244

I.左移–4820,只能右移–2482,扑街。

II.右移–0248,只能左移,2482,扑街。

下面我们证明可以在任意位置生成8,(这样也就同时证明了这个数最小是8)。

由于新生成的数只能是2,我们可以很容易地形成4000和0004的情形,同样地由于对称,只考虑4000的情形。

8出现在:

第一格:右移再左移–2420或2402,右移–2242,连续左移。

第二格:右移再左移–2402或2420,右移–2242,连续左移–8420或8402–右移。

和上一次的证明不同,由于这里的4000和0004是可以在两个2的时候我们自主选择方向的,而不是4242或2424这种被动的局面,所以只需证明到这里,由对称性就可以证得可以在本行任意位置生成8了。

于是,在倒数第二行的任意位置可以生成32。同理倒数第三行以64为最小单位,可以生成256;第一行以512为单位,可以生成2048。

原文链接:http://www.guokr.com/question/546311/