MathLabs

第3問

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

三色は同時に変化するが、一個の駒では三色の偶奇を揃えられない。

(N0,N1,N2)(mod2)isinvariant(N_0,N_1,N_2)\pmod2 is invariant
詳しい解説

一手は二個を除き一個を加えるため、三色それぞれの偶奇が反転する。n=3q なら各色は 3q^2 個で、偶奇ベクトルは (0,0,0) または (1,1,1)。一個だけの状態は 1 が一つ、0 が二つなので不可能。