价值100元的华容道无解性证明

2018-02-05  本文已影响0人  ibunny

本文送给欠我100元的某小三。

1. Intro

最近华容道很火,可惜曹操去世得早,不然也能蹭个何猷君的热搜。最近同样很火的游戏,还有一个头脑王者,可惜前几天由于未可知的原因被封了。

离开了头脑王者的我,就像高考前遇到车祸的考生。

为了检验自我的智商是否一下跌落到倔强青铜,我坚定地戳开了华容道小程序,准备接受知识的洗礼。

可谁能想到,我第一道题,就遇到了滑铁卢。

图1

棋盘到达图1这个状态之后,我又瞎戳了个三五分钟,仍是无解。

出于程序员的自我修养,我开始考虑,这会不会是小程序的bug?

也就是说,编写小程序的人并不是从棋盘原始状态(图2)出发,按上下左右移动的规则打乱棋盘,而是 瞎几把 随机初始化棋盘?

图2

为了证明我的猜想,我去洗了个头,接着开启了头脑风暴。

2. 随意证明一发

要如何证明图1状态的华容道是无解的?

我的不知道严不严谨的证明是:逆向思维。即证明从图2的原始状态是无法通过上下左右平移到达图1的状态的。

1 2 3 4 5 6 7 8 9 10 13 14这几个数字都各就各位之后,我们只需要关注右下角的2x2的4个方格。

如图3所示,空格以0表示,在这个2x2的方块内,我们从原始状态出发,经过多次平移,11 12 15这三个数字只可能出现如下几种排列方式。因为不论怎么移动,这四个格子都相当于做了顺时针或逆时针的旋转,而不可能出现图1中1215两两交换的局面。

图3

但是我这个糙证明被不愿意透露姓名的小三同学否定了,原因是11 12 15可以借助其他位置(如10 14 7 8)改变顺序。

为了反驳这位同学的观念,我提出了牛宝宝猜想:即,当除右下角的2x2方格以外的所有数字都归位时,该2x2方格中的数字只能有图3中的几种状态;换言之,如果该2x2方格中出现了其他状态,则1 2 3 4 5 6 7 8 9 10 13 14这几个数字的位置必然是打乱的。

然而,由于缺乏强大的理论支撑,证明陷入僵局。

可是,作为图灵的后人,怎么能被这点困难打倒呢?这岂不是告诉世人,我就是倔强青铜,倔强青铜就是我。

为了证明我王者的实力,我打开了万能的谷歌,准备抄抄别人的答案。奇妙的是,关于这个问题竟然只有一些只言片语的解读。最终,经过我的不懈努力,终于让我catch到了一个关键字:逆序数。

3. 从逆序数的角度证明无解性

3.1 逆序数

逆序数是什么?我相信大家和我一样,是懵逼的。
不过我相信,通过我下面的浅显易懂的解读之后,你会在半分钟之内决定关掉这个网页。

逆序数是什么,我相信任何一个修过线性代数,学过行列式的人,都不会记得的。像我就不记得逆序数就是一个排列中所有逆序的总数
没错,这就是一句废话。我们还是来看一个例子吧。

逆序数计算

2 7 8 1 3这个排列中,如果标准次序是从小到大的话,那么逆序对有:(2, 7), (2, 8), (2, 1), (2, 3), (7, 8), (7, 1), (7, 3), (8, 1), (8, 3), (1, 3),共5个,因此这个排列的逆序数就为5

如果你坚持过了半分钟,到了这,恭喜你,你已经知道了逆序数是啥了。不如再坚持半分钟,来看一下神奇的逆序数定理。

逆序数定理

逆序数定理1:一个排列中的任意两个元素对换,排列的奇偶性会改变。

Q1:什么是排列的奇偶性?

Q2:什么是元素对换?

Q3:定理1证明?
我估计你们也不想看,有兴趣的自己戳链接:证明

3.2 逆序数证明无解性

再贴一下图,我们要证明的是下面这个状态的华容道是无解的。怎么利用逆序数定理来证明呢?

首先,我们把这个棋盘按行拉长成一个队列:
s1 = 1 2 3 4 5 6 7 8 9 10 11 15 13 14 12 16
空格用16表示。

显然 ,原始状态的队列为:
s0 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

把它们两都看成排列的话,利用我们刚刚学的知识,s1的逆序数为:(15, 13), (15, 14), (15, 12), (13, 12), (14, 12),共5个。而s0的逆序数为0个。

是时候甩出我们的华容道定理了。

华容道定理第一弹

华容道定理1:按照游戏规则移动方块不会改变排列的逆序数奇偶性。

这是网上很多人提的一个证明思路。
下面我们来证明一下这个定理是错误的。【接受反驳】

证明:
根据逆序数定理,上下平移或左右平移,相当于交换了某个元素和空格元素的顺序,排列奇偶性会发生改变。

比如将图2原始状态中的12向下移动到15的右边,则s = 1 2 3 4 5 6 7 8 9 10 11 16 13 14 15 12,相当于交换了1216的位置,这时逆序数为7,而原始逆序数为0,奇偶性发生改变。

华容道定理第二弹

华容道定理2:若某状态的排列的逆序数加上空格元素行号和列号的奇偶性 ≠ 原始状态的排列的逆序数加上空格元素行号和列号的奇偶性,则该状态是无解的。

一句话证明:
空格元素和某个元素交换位置,则排列的逆序数的奇偶性就改变一次。交换后空格元素的行号或者列号会加1或减1,即行号,列号之和的奇偶性也改变一次。

要看完整证明,戳:完整证明

还是以刚刚的s = 1 2 3 4 5 6 7 8 9 10 11 16 13 14 15 12为例,此时该排列的逆序数加上空格元素行号和列号 = 7+3+4 = 14,仍为偶数。

而我们要证明无解的状态(图1)的排列 s' = 1 2 3 4 5 6 7 8 9 10 15 13 14 12 16,其逆序数加上空格元素行号和列号 = 5+4+4 = 13,为奇数,很明显,这是无解的啦。

得证。

Source

上一篇下一篇

猜你喜欢

热点阅读