15 puzzle

作者: , 共 892 字

注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。

游戏规则很简单,\( 4\times4\) 的方格里有 15 个方格块,标记为 1 , 2 到 15 ,有个位置是空的。每次方块可以滑动到旁边的空格中(与华容道类似)。问是否可以变成左下图这种状态?

一个明确的问题是从左下图这种状态变到右下图的标准状态。听说有人靠卖这个积木游戏赚了大钱,并且设定了一个高额奖金。

  1    2    3    4    ->      1    2    3    4       
  5    6    7    8    ->      5    6    7    8       
  9   10   11   12    ->      9   10   11   12      
 13   15   14         ->     13   14   15           

定理:记空格为 16。初始状态为\( 1,2,\cdots, 16\) 的一个排列\( \pi\) 。方格黑白相隔染色。当且仅当\( \pi\) 为偶排列且空格位于白色格 或者 \( \pi\) 为奇排列且空格位于黑色格,可以移动到标准状态。

必要性:每次移动,\( \pi\) 的奇偶性都改变,空格所在格子颜色亦发生改变。

充分性:按照1,2,3,4,5,9,13,6,7,8,10,14,11,12,15的顺序把格子移到正确的位置上即可。

推论:故从右上图是不可能变成左上图的。没有人能拿到奖金。

注 1 :一个排列\( \pi_1, \pi_2, \cdots, \pi_n\) 的奇偶性定义为\( \prod_{i>j}(\pi_i-\pi_j)\) 的符号。正为偶排列,负为奇排列。任意调换两个数的位置都会改变其奇偶性。

注 2 :此结论和证明对\( n\times n, n\geq 2\) 的情形都有效

附录

Q. E. D.

类似文章:
在 MIT BBS 上看到一个有趣的题目
本文将证明:最佳约会策略里提到策略,忽略前 37%的对象,然后在剩下的对象里挑第一个比前 37%都好的对象,这个策略是最优的。更准确地,我们将证明:任何约会策略的成功概率都不可能超过\( \frac{u}{n}\sum_{i=u}^{n-1}\frac1i\) ,其中\( u\) 为满足\( \sum_{i=u}^{n-1}\frac1i\geq 1\) 的最大值。这个\( u\) 大约为 37%,最后成功的概率大约为 40%。
以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的overhang 堆积木 - 能伸出桌面多远?。今天这次课,来自 Aarhus 的Peter Bro Miltersen讲了一个很有趣的游戏问题。
数学 » 圆周率
今天 gezhi 上有一篇关于\( \pi\) 的八卦文章,里面讲到了\( \pi\) 的计算问题。但我对其中的一些数据起了疑心,并不是说数据错了,而是作者所用的数据实在是太老了。
注: 这个问题来自China Theory Week 2008的 Open Problems Session。
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮,可以选择「黑色」「白色」或「弃权」(也就是 pass ,不作猜测的意思)。小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择。如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。
数学 » 数学游戏, 概率
蚁迹寻踪及其他数学探索》提到一个游戏:
相似度: 0.058
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
相似度: 0.058
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个\( 2\times2\) 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
相似度: 0.055
\( n\) 枚硬币排成一排,两人轮流取,每人每次可取其中一枚或者相邻的两枚。
编程 » Baidu, Google, IT评论
Google 更懂中文我拿不出什么确切的证据(虽然我已经这样认为),但下面的数据是否能说明 Google 确实更懂阅微堂呢?
转载的。作者 84 年的。同龄的都看看吧。