棋盘上的越狱游戏

Youtube上面有一个很有趣的玩弄数字的频道Numberphile,最近它们发布了一个视频来解释一个很古旧的谜题的解法。这个谜题的规则很简单,问题看上去也很简单,可是当你去尝试解决的时候却会发现这货其实并没有那么简单,最有趣的是,这个最后看上去好像很复杂的问题其实只需要会四则运算就能解决,听上去是不是很好玩呢?如果你的英文还行,访问Youtube也没有障碍的话,现在就可以点击上面的链接去一探究竟。当然如果你懒,也可以听我在这里说,毕竟这就是这篇文章的目的。

首先你有一个国际象棋棋盘,这个想必大家都已经熟悉了:

dmv0102b

其次你有一堆圆形的像围棋一样的棋子,就不要吐槽为什么要在国际象棋棋盘上下围棋了,思路不广哪来的谜题呢。

至于规则也很简单:

屏幕快照 2013-12-25 下午1.06.17

首先我们在某一格里有一个棋子

屏幕快照 2013-12-25 下午1.06.25

然后我们在它的上面和右边各放一个棋子,最后把原来的棋子拿掉。游戏前进的方向就是绿色箭头指向的方向。

当然了,如果某个棋子的上面或右边已经有一个棋子了,那么我们就必须先将占位的棋子移走才能移动那个棋子。

好了,规则就是这么简单,问题也不复杂,我们现在有这么一个“监狱”,就是下图被圈起来的部分:

屏幕快照 2013-12-25 下午1.42.09

监狱里关着3个棋子,那么请问,使用上面的规则,我能让这个监狱里没有棋子吗?你可以现在就拿张纸画一画,然后再往下看。

.

.

.

.

.

如果你已经试过了,可能就会发现,这个棋盘不够用,那么我们就换个大点的,让这个棋盘向上向右都是无限延伸的,再来试一试。

.

.

.

.

.

好了,试到现在你的纸应该已经花到没法看的地步了,不过很遗憾,那个监狱里似乎还有人在里面。到现在大部分人应该都觉得,这个看上去很弱智的问题,是做不到的,那么下一步就变成了,如何证明这事是不可能的呢?证明做不到是个很麻烦的问题,在大部分情况下几乎是不可能的,Quora上面有这么一个讨论串 How is it possible to disprove the existence of anything with certainty? 说的就是这个问题。不过还好我们这里只是一个纯粹的数学问题,想要证明这是不可能的仍旧是可能的,并且很简单,当然,简单的前提是你知道怎么做_(:з」∠)_

证明的思路是,我们需要一个“不变量”,这个量在我每次做完移动后都是不变的。那么显然个数不行,因为每次移动都会一个变成两个,于是就给每个格子赋一个权重吧,然后让每个格子的权重等于其上面的和右边的格子权重的和,这样的话我移动一个棋子,移动前后其所处格子的权重是不会变的,就像这样:

屏幕快照 2013-12-25 下午2.09.23

那么给所有的格子都赋予一个权重并且满足这样的条件是可能的么?回想一下移动棋子的规则,每次移动棋子都会在其上方和右方放置一个新的棋子,这正好是是成对角线对称的形式:

屏幕快照 2013-12-25 下午2.09.37

而我们的棋盘正好也是对角线对称的!也就是说我只要给两个NEW赋予相同的值,让它们等于OLD的一半就可以了!

现在我们就可以给棋盘赋值啦,起始点当然是左下角,就给个最简单的,\(1\)好了,然后是两个最近的格子给\(1/2\),像这样:

屏幕快照 2013-12-25 下午2.38.36

这样我们就可以将棋盘的每一个格子赋予一个权重了。好了,证明最困难的部分就到此为止了,后面的部分不过就是基本的演算了,有了这些,想必有不少人已经知道该怎么做了,是的,就像这样:

屏幕快照 2013-12-25 下午2.45.55

我们现在有一个带权重的棋盘,以及在左下角里的3个犯人,为了将他们移动出去,绿色区域的权重必须至少要等于监狱里的权重才行,因为无论做多少步移动,初始的权重是不会变的,而如果我能将所有的棋子移出监狱,那么他们最后呆在的绿色区域权重相加就必须等于监狱内的权重。可是如何算呢?这个绿色的部分也不是规则形状的,那么干脆就算整个棋盘的权重后减掉监狱部分的好了。即使这样,一个二维的数列看上去也很难算,那么干脆我们就从最下面一排开始吧,那么最下面一排的值就是:

\(S=1+1/2+1/4+1/8+\dots\)

这就是一个典型的等比数列了,如果上过初中的话应该都可以解决,不过之前说了,我们只需要四则运算就能解决这个问题,那么作为一个小学生,我们要怎么解呢?我们可以两边都乘上一个2来看看:

\(2S=2+1+1/2+1/4+1/8+\dots\)

咦,自2之后的那部分不就是之前的\(S\)么?好,那么我们就能写成:

\(2S=2+S\)

这就太简单了 \(S=2\)。 哇,我们居然用一堆无限的数加出了一个有限的值,是不是很有趣呢?如果你觉得有趣,那么稍微跑一下题,试试这个问题如何:

\(A=9/10+9/100+9/1000+9/10000+\dots\)

这里的A又等于多少?提示,你可以试着在两边同时乘以\(10\)来看看。那么这个跑题的部分先放在一边,回到棋盘的部分,如法炮制我们可以把每一行都加起来,最后的结果就是这样:

屏幕快照 2013-12-25 下午3.04.27

想必到现在你已经是老油条了,这个新的数列加法也不用我说什么了吧,答案就是\(4\)。好了,现在我们知道,监狱部分的权重是\(2\),监狱外的权重和也是\(2\),所以...似乎是可以的?可是别忘了,监狱外有无穷个格子,也就是说在有限步骤里是填不满的,也就是说,在有限的一盘游戏里,你是没法将监狱里的棋子全部移动出来的,也就是说,我们证明了这个游戏是不可能的。怎么样,这个看上去很简单的游戏是不是很有趣呢?

最后剩下一点,让我们回到跑题的那部分,想必你已经算出来了,\(A=1\),不过我们把那堆加法的数字换个方法来写:

\(9/10+9/100+9/1000+9/10000+\dots=0.9+0.09+0.009+0.0009+\dots=0.99999999999 \dots\)

所以

\(0.99999999\dots=1\)

One thought on “棋盘上的越狱游戏

发表评论

电子邮件地址不会被公开。 必填项已用*标注