（Ｑ）２^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-1＋４^n-2＋・・・＋１）であるから，２^n×２^n−１は３で割り切れるとする方が簡単かももしれない．

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