15パズルに対するロイド=ジョンソン偶奇不変量

ステップ1(横スライド)。 空白が同じ行内で左右にスライドするとき、$15$ 個の数字タイルの行優先順での並びは一切変わらず、空白も行 $r(s)$ にとどまる。したがって $\Delta N = 0$ かつ $\Delta r = 0$ であり、$N(s) + r(s)$ は不変である。

ステップ2(縦スライド)。 空白が上下にスライドするとき、空白の元の位置へ移動するタイル $t$ は $15$ 個の数字タイルの行優先列の中でちょうど $3$ つ分位置がずれる。その $3$ 個の各タイルを飛び越えるたびに組 $(t, u)$ の転倒関係が反転し、$N(s)$ は1タイルあたり $+1$ または $-1$ 変化する。合計の変化量は $\Delta N \in \{-3, -1, +1, +3\}$ で常に奇数である。同時に $\Delta r \in \{-1, +1\}$ も奇数なので、$\Delta(N + r)$ は偶数となる。

ステップ3(14と15の交換)。 空白を行 $r = 4$ に固定したままタイル $14$ と $15$ を入れ替えると、$\Delta r = 0$ のまま $N(s)$ が $+1$($0$ から $1$ へ)変化する。よって初期状態($1 + 4 \equiv 1 \pmod 2$)と完成状態($0 + 4 \equiv 0 \pmod 2$)で $(N + r) \bmod 2$ が異なり、いかなる合法なスライド列でも完成状態に到達できないことが証明される。