【１】ドミノ問題
まずは有名な不可能問題を紹介しよう．
（Ｑ）隅とそのちょうど反対側の隅にあるマス目を切り取った８×８のチェス盤を３１個のドミノ（２マスサイズ）では覆いつくすことはできるだろうか？
■□■□■□■
■□■□■□■□
□■□■□■□■
■□■□■□■□
□■□■□■□■
■□■□■□■□
□■□■□■□■
■□■□■□■
（Ａ）チェス盤を市松模様に塗ると３２の黒マス，３２の白マスができる．２つの向い側の白い角を取り除くと３２の黒，３０の白ができる．しかし１枚のドミノを置くとき，黒と白の正方形が１つずつ覆われるからどうしても２つの黒い正方形が残ってしまう．
このように隅を切り取られたチェスボードでは白か黒どちらかのマス目が多くなるため，ドミノでは覆いつくすことができないのである．それでは・・・
（Ｑ）どの２つの正方形を切り取ろうとも，切り取った正方形の色が異なるならば必ずドミノを敷き詰めることができるだろうか？
（Ａ）yes.敷き詰め方の具体的構成法は自分で考えてみてほしいのだが，８×８のマス目を６４個の数珠状の輪にする．２つの正方形が除かれると輪は２つの部分に切断される．２つの正方形が違う色であれば，切断された部分は必ず偶数の正方形を含むことになる．
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
９×９マスの将棋盤ではどうだろうか？ 隅とそのちょうど反対側の隅にあるマス目を切り取った将棋盤は７９マスであるから，ドミノで覆いつくすことができないことは明らか．そこで隅を１マスだけ切り取った将棋盤について考えることにするが，敷き詰めが可能であることは簡単にわかる．
それでは
（Ｑ）どの１マスを切り取ろうとも，ドミノを敷き詰めることができるだろうか？
（Ａ）No.将棋盤のマス目(i,j) (i=1~9,j=1~9)に対してi+jの合計を考えると偶数の場合と奇数の場合があり，８１マス全体での合計は偶数になる．１枚のドミノで覆われる２マスのi+jの合計は奇数であるから，４０枚のドミノで覆われる２マスのi+jの合計は偶数．したがって，i+jの合計が奇数のマス目（奇数点）を切り取った場合，８０マスの合計は奇数となって，敷き詰めは不可能である．
９×９のマス目は数珠つなぎにならないので，たとえば，隅の隣りにある１マスを切り取った場合，一番隅の正方形が残りの部分から孤立するのである．こうして１５パズルの場合の結論，反転の個数の合計が偶数ならば解くことは可能であるが奇数ならば解法は存在しない，と類似の結果となった．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【２】トロミノ問題
（Ｑ）Ｌ字型のトロミノ
□
□□
を合同な４片に分割せよ．
（Ａ）
□□ ■■ □□ □□
□■ ■□ □□ □□
□■■□ □□□□ ■□□□ □□□■
□□□□ □□□□ ■■□□ □□■■
（Ｑ）２^n×２^nの格子盤から１個のマス目を切り取ったものは，すべてＬ字型トロミノ
□
□□
で覆いつくすことができるか？
（Ａ）２×２から１マス切り取ったものはトロミノであるから，ｎ＝１のとき覆いつくすことができることは明らか．ｎのとき覆いつくすことができると仮定して，２^n+1×２^n+1の格子盤から１マス切り取ったものを考える．
この格子盤を４等分して，中央部から
□
□□
を取り去ると，１マス取り去られた２^n×２^nの格子盤が４つできる．仮定より，これら４つの格子盤はトロミノで覆いつくすことができるから４つ合わせれば任意の１マスを切り取った２^n+1×２^n+1の格子盤になる．
□□□□□□□□ ■■■■□□□□ ■■■■□□□□
□□□□□□□□ ■■■■□□□□ ■■■■□□□□
□□□□□□□□ ■■■■□□□□ ■■■■□□□□
□□□□□□□□ ■■■■□□□□ ■■■ □□□
□□□□□□□□ □□□□■■■■ □□□□ ■■■
□ □□□□□□ □ □□■■■■ □ □□■■■■
□□□□□□□□ □□□□■■■■ □□□□■■■■
□□□□□□□□ □□□□■■■■ □□□□■■■■
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
こうして数学的帰納法による証明が完了したというわけであるが，ところで２^n×２^n−１が３で割り切れることが問題の前提条件として必要である．フェルマーの小定理より
２^n×２^n＝４^n＝１ （ｍｏｄ ３）
であるが，連続するｋ個の整数の積がｋ！で割り切れることを使えば（フェルマーの小定理のごとき牛刀をもちだすまでもなく）３で割り切れることを証明することができる．
（２^n−１）２^n（２^n＋１）は６で割り切れる
→（２^n−１）（２^n＋１）は３で割り切れる
→２^n×２^n−１は３で割り切れる
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【３】ペントミノ問題
（Ｑ）ペントミノ
□
□□□□
を４等分せよ．
（Ａ）
□□□□
□□□□
□□□□
□□□□
□□■■■■□□□□□□■■■■
□□■■■■□□□□□□■■■■
■■■■■■□□□□■■■■■■
■■■■■■□□□□■■■■■■
正方形を正三角形に変えるとスフィンクスになる．スフィンクス
△
△▽△▽△
も同様に図形を４つに等しく分けることができる．
△
△▽△
△▽▲▽△▽△▽▲
▲▼▲▼▲▽▲▼▲▼▲
切り分けられた図形は再びスフィンクスになるが，この関係は外側にも内側にも無限に続くことになるので，次々に大きなスフィンクスを作り上げることができる（平面充填）．
（Ｑ）ペントミノは何種類あるか？
（Ａ）ペントミノは１２種類ある．
□□□□□ □ □ □ □□□ □
□□□□ □□□□ □ □ □□□
□□□ □ □
□ □ □ □ □ □ □□□
□□□ □□ □□□ □□□ □□ □□
□□ □ □ □□
そのうち
□ □ □□□
□ □□ □□
□□□ □□
を除く９種類は４個の合同な片に分解できることが確かめられている．しかもその形は一意である．
□□□□
□□□□
□□□□
□□□□
■■■■□□■■■■■■
■■■■□□■■■■■■
■■■■■■□□■■■■
■■■■■■□□■■■■
□□□□
□□□□
□□□□
□□□□
（Ｑ）ペントミノで長方形を敷き詰めることができるものは何種類あるか？ また，長方形を敷き詰めるのに必要な最小枚数は何枚か？
□□□□□ □ □ □
□□□□ □□□□ □□
□□
（１） （２） （１０） （２）
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【４】ｎオミノ問題
（Ｑ）同じ大きさの正方形の辺と辺をつなげたタイルで，正方形をｎ枚使ったものをｎオミノと呼ぶ．ｎオミノは何種類あるか？
（Ａ）回転や反転で同型になるものは同じと数えると，モノミノ（１），ドミノ（１），トロミノ（２），テトロミノ（５），ペントミノ（１２），ヘキソミノ（３５），ヘプトミノ（１０８），・・・．別に数えると，モノミノ（１），ドミノ（２），トロミノ（６），テトロミノ（１９），ペントミノ（６３），ヘキソミノ（２１６），ヘプトミノ（７６０），・・・
ｎオミノの種類はｎとともに急速に増加する．前者の個数をＰn，後者の個数をＱnと表すと
ｎ Ｐn Ｑn ｎ Ｐn Ｑn
１ 1 1 10 4655 36446
２ 1 2 11 17073 135268
３ 2 6 12 63600 505861
４ 5 19 13 238591 1903890
５ 12 63 14 901971 7204874
６ 35 216 15 3426576 27394666
７ 108 760 16 13079255 104592937
８ 369 2725 17 50107911 400795860
９ 1285 9910 18 192622052 1540820542
大きなｎに対して
Ｑn 〜 ａ^n （ａ＝３．７２〜４．５）
Ｐn 〜 Ｑn／８
という漸近評価が得られている．
この数え上げは
［参］「スチュアート教授のおもしろ数学入門」日経サイエンス社
から転載したものであるが，漸近評価を含む数え上げについては
コラム「飽和炭化水素の構造異性体数」
が参考になる（はずである）．
ちなみに，長方形を敷き詰めることができるものは
モノミノ （１／１）
ドミノ （１／１）
トロミノ （２／２）
テトロミノ （４／５）
ペントミノ （４／１２）
ヘキソミノ （１０／３５）
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝