价值100元的华容道无解性证明
本文送给欠我100元的某小三。
1. Intro
最近华容道很火,可惜曹操去世得早,不然也能蹭个何猷君的热搜。最近同样很火的游戏,还有一个头脑王者,可惜前几天由于未可知的原因被封了。
离开了头脑王者的我,就像高考前遇到车祸的考生。
为了检验自我的智商是否一下跌落到倔强青铜,我坚定地戳开了华容道小程序,准备接受知识的洗礼。
可谁能想到,我第一道题,就遇到了滑铁卢。
图1棋盘到达图1这个状态之后,我又瞎戳了个三五分钟,仍是无解。
出于程序员的自我修养,我开始考虑,这会不会是小程序的bug?
也就是说,编写小程序的人并不是从棋盘原始状态(图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中12
和15
两两交换的局面。
但是我这个糙证明被不愿意透露姓名的小三同学否定了,原因是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)
, ,共5个,因此这个排列的逆序数就为(1, 3)
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
,相当于交换了12
和16
的位置,这时逆序数为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,为奇数,很明显,这是无解的啦。
得证。