まずは有名な不可能問題を紹介しよう．次の問題はおそらく読者も知っているだろう．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】ドミノ問題

（Ｑ）隅とそのちょうど反対側の隅にあるマス目を切り取った８×８のチェス盤を３１個のドミノ（２マスサイズ）では覆いつくすことはできるだろうか？

　　　■□■□■□■

　　■□■□■□■□

　　□■□■□■□■

　　■□■□■□■□

　　□■□■□■□■

　　■□■□■□■□

　　□■□■□■□■

　　■□■□■□■　

（Ａ）チェス盤を市松模様に塗ると３２の黒マス，３２の白マスができる．２つの向い側の白い角を取り除くと３２の黒，３０の白ができる．しかし１枚のドミノを置くとき，黒と白の正方形が１つずつ覆われるからどうしても２つの黒い正方形が残ってしまう．

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

（Ｑ）どの２つの正方形を切り取ろうとも，切り取った正方形の色が異なるならば必ずドミノを敷き詰めることができるだろうか？

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

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

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

　それでは

（Ｑ）どの１マスを切り取ろうとも，ドミノを敷き詰めることができるだろうか？

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

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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝