敷き詰め問題

質問

宿題として出されたのですが、証明の仕方がわかりません。数学的帰納法を使えばできると言われたのですが…。

田の字から四半分を除いたような、単位正方形３個をＬ字状に隣接させた形のタイルを多数用意します。一辺の長さ2^n（n=1,2,3,…）の正方形の床をこのタイルで敷き詰めていくと、正方形の面積4^nは３で割って１余るので、どこかに単位正方形１個分の空きが生ずることになります。
そこで、逆に単位正方形１個分の空きをこの床の単位幅格子のどの目に指定しても、それ以外の部分は必ずこのタイルでちょうど敷き詰めできることを証明してほしいです。

問題がややこしくてすいません。教えてください。お願いします。

回答No.1

fushigichan · ベストアンサー

kyon1110さん、こんにちは。

*****************命題*********************************
一辺が2^nという正方形は、Ｌ字型のタイルを敷き詰めていくと
１単位正方形分だけの空きが生じる。
******************************************************

上の命題を、数学的帰納法で証明する。

1)n=1のとき
2^1*2^1=4
この正方形は、一つのＬ字型で埋まり、単位正方形１つが残る。

2)n=kのとき命題が成り立っているものとする。(n≧2)
2^k*2^k=4^kという面積が、ｐ個のＬ字型＋１個の単位正方形と書ける。

3)n=k+1のときも成り立つことを示せばよい。
2^(k+1)*2^(k+1)=2^k*2*2^k*2=4^k*4
ここで、4^kという面積の正方形は、ｐ個のＬ字型と１個の単位正方形で敷き詰められる。
したがって、その４倍なので４Ｐ個のＬ字型で埋められ
さらに、４単位正方形余る。
さて、1)より、４単位正方形は、１個のＬ字型＋１単位正方形であったので
単位正方形のあまりを、４つの部分の端っこに指定すれば
n=k+1のときは、全部で（４ｐ＋１）個のＬ字型＋１単位正方形となる。

1)2)3)より、全ての自然数nについて、命題は成立する。

さて、次に、どの部分に単位正方形をとっても、命題が成立することを考えてみる。

1)たとえば、2^1*2^1の正方形のときは、
左上、右上、右下、左下の、どこに単位正方形をとっても、残りは一つのＬ字型である。

2)2^2*2^2を考える。これは、４×４＝１６とおりの単位正方形のおき場所があるが、
どこに置こうとも、それを含んだ２×２の正方形は一つ決まる。
それは、一つのＬ字型＋一つの単位正方形となる。
残りの２×２の正方形３つは、どれも２つのＬ字型で埋められることは容易に理解できる。

3)今、2^n*2^nの正方形を考える。
この中の、単位正方形の置く場所を左上から行列のように
(i,j)番目にあると仮定する。
すると、(i,j)番目が入っている２×２という正方形が一つ決まる。
(i,j)番目が入っている正方形以外の、2^(n-1)*2^(n-1)-1個の２×２正方形は、
1)2)より、Ｌ字型のみで埋められる。
(i,j)番目が入っている２×２正方形は、1)より、どこに単位正方形を持ってきても
一つのＬ字型＋一つの単位正方形で埋まる。
これは、すべての自然数1≦i≦2^n,1≦j≦2^nについても成り立つ。
（(1,1)≦(i,j)≦(2^n,2^n)であるから、(i,j)をどこにとってもよい。）

1)2)3)より、命題は、単位正方形を、どこに置いても成り立つことが証明された。

回答No.3

fushigichan

＃１fushigichanです。＃２さん補足ありがとうございます。

＞残りの２×２の正方形３つは、どれも２つのＬ字型で埋められることは容易に理解できる。

確かに、容易には理解できないかもですね・・こう書いた意図は、前半で、

＞さて、1)より、４単位正方形は、１個のＬ字型＋１単位正方形であったので
単位正方形のあまりを、４つの部分の端っこに指定すれば
n=k+1のときは、全部で（４ｐ＋１）個のＬ字型＋１単位正方形となる。

という証明をしましたので、それを用いて、単位正方形を
分割したあとの３つの正方形の中心に持ってくれば、という意味です。
（４つの部分の端っこに持ってくれば、ということ）詳しく書けばよかったですね。

全体を４等分したときに、単位正方形が入っている(i,j)番目の格子は、その４つの部分のどれかになります。
（第一、第二、第三、第四象限のような感じです）
それ以外の３つの大きな正方形は、原点の部分に単位正方形を持ってくれば
残りはＬ字型で埋められ、原点中心の３つは一つのＬ字型で置き換えられますから
命題は成り立つ、という感じです。

大変難しい問題だと思います。ご参考になればうれしいです。

お礼

大変参考になりました！！わかりやすいご回答をありがとうございました。

回答No.2

pancho

#1のfushigichanさんの回答方針で良いと思われますが、
　＜残りの２×２の正方形３つは、どれも２つのＬ字型で埋められることは容易に理解できる。＞
が間違っているようです。

この部分の改良として、
3)n=kの時に成り立っているので、n=k+1の時は、
　3-1)正方形を一辺k^2の小さい正方形に４等分する
　3-2)単位正方形を含んだ正方形は、n=kの時の正方形と同サイズなので、埋め尽くせることが証明されている
　3-3)残りの３つの小正方形は、大正方形の中心部分に相当する単位正方形１つを残してＬ字状のタイルで埋め尽くせることが証明されている
　3-4)この単位正方形３つは、ちょうどＬ字状のタイルと同じ形になるので、このタイル１つで埋められる
これで、n=k+1の時の時にも埋め尽くせることが証明された

図示すると、こんな感じです。
┌──────┬──────┐
│　　　　　　│　　　　　　│
│　　　　　　│　　　　　　│
│　　　　　　│　　　　　　│
│　　　　　　│　　　　　　│
│　　　　　　│　　　　　　│
│　　　　　┌┼┐　　　　　│
├─────┴┼┼─────┤
│　　　　　　├┘　　　　　│
│　　　　　　│　　　　　　│
│　　　　　　│　　　　　　│
│　　　　　　│　　　　　　│
│　　　┌┐　│　　　　　　│
│　　　└┘　│　　　　　　│
│　　　　　　│　　　　　　│
└──────┴──────┘

以上。

お礼

大変参考になりました！！わかりやすいご回答をありがとうございました。