「夫子憮然曰、鳥獣不可與同羣。吾非斯人之徒與、而誰與。
「論語」微子、第十八、六

2013/07/25

チェス盤の上の石二つ(解答)

昨日のパズル の解答。 不可能であることが、以下のようにパリティ(偶奇性)を用いて簡単に証明できる。

チェス盤の市松模様に注目し、二つの石が同色のマスにある場合を「偶配置」、 異なる色のマスにある場合を「奇配置」と呼ぶことにする。 異なるマスに黒石一つ、白石一つを置く方法は 64 かける 63 通りあるが、 このうち、偶配置は 64 かける 31 通り、奇配置は 64 かける 32 通りあって、後者の方が 64 通り多い。 一方、ある配置からどちらかの石を上下左右のどのマスに動かしても、 偶配置は奇配置に、奇配置は偶配置に変わることに注意せよ。 よって、この動かし方を続ける限り、 辿った配置における偶配置と奇配置の数の差は 0 か 1 にしかならない。 しかし、全ての配置では奇配置の方が 64 多いのだった。 ゆえに、全配置を一度ずつ辿ることはできない。

この問題の出典は、2001 年のモスクワ数学オリンピックだそうだ(その割にはちょっと易しめ?)。 私は Futility Closet で知った。