01 転倒数 I
0
左にある数 ＞ 右にある数、となるペアの数
1手動かして変化を観察
動かすたびに、数学が見える。
動く数字。
変わらないひみつ。
まずは遊んでみよう。気になったら「数理を見る」で、盤面の裏側へ。
フリープレイ
CLEAR!空白のとなりのタイルをタップ
もうひとつの盤面に挑戦
タップ・クリックで移動 ／ 矢印キーで空白を移動
DISCOVER THE PATTERN
盤面の裏側をのぞく
変わるものと、変わらないもの。
数字を動かすと、盤面の「偶数・奇数」は
どう変わるでしょう？
スイッチを ON にして観察しよう
空白を 9 番のタイルと考えます。
左上から行ごとに読むと、次の置換になります。
左上から行ごとに読むと、次の置換になります。
02 空白の位置 (r, c)
(3, 3)
左上は (1, 1) · r + c = 6
行 + 列の偶奇に注目
INVARIANT / 不変量
P = (I + r + c) mod 2
動かしても、この偶奇は変わりません。
ゴールの P
＝現在の P
履歴を見る 最近の12状態
| 手数 | 転倒数 I | 空白 (r,c) | r+c | I+r+c | パリティ |
|---|
下ほど新しい状態です。最後の列を見比べよう。
なぜ変わらない？ 3 × 3・4 × 4・5 × 5 共通
空白も n² 番のタイルと考えると、1回の合法手は空白と隣接タイルの1回の交換です。置換の偶奇、つまり転倒数 I の偶奇は必ず反転します。
同時に、空白は上下左右に1マス移動するため、r + c の偶奇も必ず反転します。
偶 + 偶 ↔ 奇 + 奇 → 和はずっと偶数
偶 + 奇 ↔ 奇 + 偶 → 和はずっと奇数
偶 + 奇 ↔ 奇 + 偶 → 和はずっと奇数
2つが一緒に反転するので、(I + r + c) mod 2 は不変です。盤面の大きさに関係なく成り立ちます。
ゴールでは I = 0、r + c = 2n なので P = 0（偶数）。ゴールと P が違う盤面は、合法手だけではゴールにたどり着けません。
mod 2 は「2で割った余り」。0 が偶数、1 が奇数を表します。