昨日のパズル の解答。 不可能であることが、以下のようにパリティ(偶奇性)を用いて簡単に証明できる。
チェス盤の市松模様に注目し、二つの石が同色のマスにある場合を「偶配置」、 異なる色のマスにある場合を「奇配置」と呼ぶことにする。 異なるマスに黒石一つ、白石一つを置く方法は 64 かける 63 通りあるが、 このうち、偶配置は 64 かける 31 通り、奇配置は 64 かける 32 通りあって、後者の方が 64 通り多い。 一方、ある配置からどちらかの石を上下左右のどのマスに動かしても、 偶配置は奇配置に、奇配置は偶配置に変わることに注意せよ。 よって、この動かし方を続ける限り、 辿った配置における偶配置と奇配置の数の差は 0 か 1 にしかならない。 しかし、全ての配置では奇配置の方が 64 多いのだった。 ゆえに、全配置を一度ずつ辿ることはできない。
この問題の出典は、2001 年のモスクワ数学オリンピックだそうだ(その割にはちょっと易しめ？)。 私は Futility Closet で知った。
