IT技术博客大学习 共学习 共进步
全部 移动开发 后端 数据库 AI 算法 安全 DevOps 前端 设计 开发者

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

Matrix67: My Blog 2014-11-25 23:02:55 累计浏览 3,800 次
本机暂存

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

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

   可以证明,我们永远不可能在 2048 当中玩出 218 这个数。

   让我们把棋盘上的所有数全部加起来,并在累加过程中不断关注当前总和的二进制表达。如果棋盘里的数分别是 2, 4, 16, 64, 16, 2 的话,累加结果的二进制表达依次为 10 → 110 → 10110 → 1010110 → 1100110 → 1101000 。你会发现,由于棋盘上的每个数都是形如 2n 的正整数,因而把它加进总和之后,这个总和的二进制表达里最多只会多出一个数字 1 (如果发生了进位,数字 1 的个数可能会不变甚至减少)。这意味着,如果最终棋盘上的所有数之和的二进制表达当中一共有 k 个数字 1 ,那就说明刚才至少有 k 个数在相加,换句话说棋盘里至少有 k 个数块。

   容易看出,每走一步之后,棋盘上的所有数之和都会增加 2 或者 4 。如果最终棋盘上出现了一个 218 ,就说明棋盘上的所有数之和至少是 218 ,那么在此之前棋盘上的所有数之和一定经历过 218 - 2 或者 218 - 4 。前者的二进制表达为 11 1111 1111 1111 1110 ,这里面有 17 个数字 1 ,超过了棋盘里总的格子数,因而显然是不可能的。后者的二进制表达是 11 1111 1111 1111 1100 ,这里面有 16 个数字 1 ,正好是棋盘里总的格子数。这说明,此时棋盘刚好被填满, 22, 23, 24, …, 217 这 16 种不同的数块各有一个。这意味着棋盘里不但没有空白的格子,也没有相同种类的数块可以合并,此时玩家直接就死掉了!因而,我们是没有办法得到 218 的。

   因此, 217 = 131072 成为了 2048 这个游戏中数块大小的一个理论上限。但是,我们真的能弄出 131072 吗?看上去,我们好像只需要构造出下图所示的局面就行了,但这个局面本身能否实现,还有待进一步讨论。 Michael Brand 猜测,理论上 131072 也是无法得到的,但他不能证明这一点。我虽然在网上看见过很多网友宣称自己打出过 131072 ,甚至有的网友发出了最后几步的视频(比如这里),但由于我从来没有看到过完整的演示过程,因而也持怀疑态度。期待万能的网友们能够提供一种简洁有效的构造解,来说明当运气足够好的情况下,我们有办法打出 131072 ;或者找到一个更好的证明方法,足以说明 131072 也是理论上不可能实现的。

原图已失效

同分类推荐文章

  1. 对基本有序的序列排序算法 (2026-06-11 17:46:49)
  2. Four Levels Of Customer Understanding (2026-05-22 21:00:00)
  3. 除法的意义 (2026-04-12 20:52:17)

查看更多 算法 文章 →

建议继续学习

  1. 由浅入深探究mysql索引结构原理、性能分析与优化 (累计阅读 16,519)
  2. 为什么算法这么难? (累计阅读 12,397)
  3. 浅谈MySQL索引背后的数据结构及算法 (累计阅读 11,902)
  4. 加州求职记 (累计阅读 11,561)
  5. 谷歌(Google)2011年校园招聘笔试题 (累计阅读 9,573)
  6. 最常被程序员们谎称读过的计算机书籍 (累计阅读 9,156)
  7. 再谈“我是怎么招聘程序员的” (累计阅读 8,791)
  8. 如何在面试中发现优秀程序员 (累计阅读 8,313)
  9. IBM面试记 (累计阅读 7,384)
  10. 数学之美:《社交网络》中Facemash算法分析 (累计阅读 7,146)