80 关于数字华容道的可解性证明

文章预览

     昨天儿子带回来一个很喜欢的玩具,叫数字华容道长这个样子: 大概就是把数字抠出来全打乱,然后要求挪动空格,还原成上图这个样子.那么我立刻就想:这件事一定能做到么?        儿子试了几次发现不一定能,老父亲证了一下: 确实有时是不能的,但一定能还原成1-15或15-1之一 ,证明针对一般的m*n矩形(m,n>2)也成立:       一方面,归纳易证所有的m*n都可以平移到只剩下一个2*2需要调整,所以最多只有两种情况       另一方面,把m*n嵌入一个巨大的k*k并补充一些数(这里k为奇数)然后考察从左到右从上到下组成的数列(忽略空格,余下k*k-1个数,例如图中即为1-15)的逆序对变化,显然每次平移空格时它不变,列方向移动空格时它变化k-1个正负1,从而逆序对数奇偶性不变.         听着楼下汪汪队动画片的声音,不知道啥时候能把这个证明讲给儿子       陈晨，09至今 ………………………………