15数码谜题：为什么有一半永远拼不回

题目

经典的 15 数码：4×4 格子里有 15 个编号滑块和 1 个空位，每次滑动一个邻块进空位。给定一种打乱布局，问：能否滑回标准顺序（1..15 排好，空格在角落）？

答案与解析

不是所有布局都能复原！ 只有大约一半可以。判据如下：

记把 15 个数字按行展开（忽略空格）的逆序数为 $N$；再记空格从底边数起的行号（底边为 1）为 $r$。则可解的充要条件是： $N + r \equiv 0 \pmod 2$

直观原因：每一步滑动，要么把某个数跨过 0 个其它数（左右移，逆序数不变、空格行号不变），要么跨过 2 个数（上下移，逆序数变化 ±2、行号变 1）。所以 $N+r$ 的奇偶性永不改变——它是这个谜题的“守恒量”。标准解的 $N=0,\ r=1$，故 $N+r$ 为奇；凡是 $N+r$ 为偶的布局，永远到不了标准解。

背后的数学

这是 1870 年代风靡美国的 15 数码谜题，曾让无数人怀疑“是不是坏了”。它实质上是研究置换群与**奇偶性（交错群 $A_n$）**的入口：可达的布局恰好构成整个置换群的一半（偶置换）。群论的“奇偶不变量”，在这里化作一句冷酷的“你这局没救了”。