■ドミノ問題(その2)

 それでは・・・

(Q)どの2つの正方形を切り取ろうとも,切り取った正方形の色が異なるならば必ずドミノを敷き詰めることができるだろうか?

(A)yes.敷き詰め方の具体的構成法は自分で考えてみてほしいのだが,8×8のマス目を64個の数珠状の輪にする.2つの正方形が除かれると輪は2つの部分に切断される.2つの正方形が違う色であれば,切断された部分は必ず偶数の正方形を含むことになる.

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

 9×9マスの将棋盤ではどうだろうか? 隅とそのちょうど反対側の隅にあるマス目を切り取った将棋盤は79マスであるから,ドミノで覆いつくすことができないことは明らか.そこで隅を1マスだけ切り取った将棋盤について考えることにするが,敷き詰めが可能であることは簡単にわかる.

 それでは

(Q)どの1マスを切り取ろうとも,ドミノを敷き詰めることができるだろうか?

(A)No.将棋盤のマス目(i,j) (i=1~9,j=1~9)に対してi+jの合計を考えると偶数の場合と奇数の場合があり,81マス全体での合計は偶数になる.1枚のドミノで覆われる2マスのi+jの合計は奇数であるから,40枚のドミノで覆われる2マスのi+jの合計は偶数.したがって,i+jの合計が奇数のマス目(奇数点)を切り取った場合,80マスの合計は奇数となって,敷き詰めは不可能である.

 9×9のマス目は数珠つなぎにならないので,たとえば,隅の隣りにある1マスを切り取った場合,一番隅の正方形が残りの部分から孤立するのである.こうして15パズルの場合の結論,反転の個数の合計が偶数ならば解くことは可能であるが奇数ならば解法は存在しない,と類似の結果となった.

===================================