■ポリオミノの問題(その9)

 まずは有名な不可能問題を紹介しよう.

(Q)隅とそのちょうど反対側の隅にあるマス目を切り取った8×8のチェス盤を31個のドミノ(2マスサイズ)では覆いつくすことはできるだろうか?

   ■□■□■□■

  ■□■□■□■□

  □■□■□■□■

  ■□■□■□■□

  □■□■□■□■

  ■□■□■□■□

  □■□■□■□■

  ■□■□■□■ 

(A)チェス盤を市松模様に塗ると32の黒マス,32の白マスができる.2つの向い側の白い角を取り除くと32の黒,30の白ができる.しかし1枚のドミノを置くとき,黒と白の正方形が1つずつ覆われるからどうしても2つの黒い正方形が残ってしまう.

 このように隅を切り取られたチェスボードでは白か黒どちらかのマス目が多くなるため,ドミノでは覆いつくすことができないのである.

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

 もちろん,将棋盤は9×9であるから隅の2個を取り除いても不可能であることはわかるが,偶数の場合,たとえば,10×10のチェス盤から隅の2個を取り除いて49個のドミノ(2マスサイズ)では覆いつくすことはできるだろうか?

 4×4のチェス盤から隅の2個を取り除いて,7個のドミノ(2マスサイズ)では覆いつくすことはできるだろうか? 10×10は手に負えないが,4×4だといろいろ試すことによって解けるかもしれない.

 2×2のチェス盤から隅の2個を取り除いて,1個のドミノ(2マスサイズ)では覆いつくすことはできるだろうか?は試す前にわかってしまう.

 チェス盤が日本の将棋盤と異なる点は,最初から交互に白黒に塗られている点である.この問題は色とは無関係であるが,白黒に塗り分けることによって,答えがNoであることが一目瞭然となってしまうのである.

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

(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パズルの場合の結論,反転の個数の合計が偶数ならば解くことは可能であるが奇数ならば解法は存在しない,と類似の結果となった.

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