MathLabs

第3問

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

3 行のガジェットは次のガジェットに必要な形を保ったまま帯を消費する。

n=3q+1 or n=3q+2n=3q+1\text{ or }n=3q+2
詳しい解説

AoPS の構成は局所的な帯の縮約を使う。駒で満たされた 3×m の帯で、境界から内側へ水平・垂直を交互に跳ぶ。同じ縮約を隣接長方形で続けられるよう、帯を境界の一行に置き換える。向きを回転すれば両方向を扱える。