【１】トロミノ問題

（Ｑ）Ｌ字型のトロミノ

　　□

　　□□

を合同な４片に分割せよ．

（Ａ）

　　□□ 　　■■ 　　□□ 　　□□

　　□■ 　　■□ 　　□□ 　　□□

　　□■■□　　□□□□　　■□□□　　□□□■

　　□□□□　　□□□□　　■■□□　　□□■■

（Ｑ）２^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−１は３で割り切れるとする方が簡単かももしれない．

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

【２】トロミノ問題（補足）

　実は，Ｌ字型レプタイルには，２^n×２^nのマス目から任意の１マスを切り取っても，Ｌ字型レプタイルを使ってカバーできる．これはＬ字型レプタイルの有名な性質で，数学コンテストで何度も取り上げられたことがある．

　証明は簡単で，数学的帰納法による．すなわち，

［１］２×２のマス目から任意の１マスを切り取っても，Ｌ字型レプタイルを使ってカバーできる．

［２］４×４のマス目から任意の１マスを切り取っても，Ｌ字型レプタイルを使ってカバーできる．（４×４のマス目の中央部にＬ字型がくるようにする）

［３］８×８のマス目から任意の１マスを切り取っても，Ｌ字型レプタイルを使ってカバーできる．（８×８のマス目の中央部にＬ字型がくるようにする）

・・・・・

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