MathLabs

第3問

無限チェス盤上で、各マスに一個ずつ置いた nn 行 nn 列のブロックに n2n^2 個の駒を置く。手は、隣接する駒を水平方向または垂直方向に飛び越えて、その直後の空きマスへ移り、飛び越された駒を取り除くことである。最後に一個だけ残せる nn を求めよ。
ステップ 4/4: 縮約を反復する
ざっくり言うと

局所ガジェットにより合同類の分類が全体構成になる。

n=1,2(mod3)⟹one piece remainsn=1,2\pmod3\Longrightarrow\text{one piece remains}
詳しい解説

n×n ブロックを幅 3 の帯と幅 1 または 2 の余りに分け、二方向に交互に帯補題を適用する。n≡1 なら余りは 1×1 の終端となり、n≡2 の余りも二方向ガジェットでそこへ縮約できる。従って 3 の倍数以外はすべて可能で、不変量と合わせて答えは 3 の倍数でない n である。