Corollaryは必然に。

このブログは「コロちゃんぬ」の提供でお送りします

数学的帰納法とパズル

「数学デー」公式Twitterでは、その場で出た話題の写真を見ることはできますが、それに辿り着いたプロセスや証明などはその場でしか聞けません(ていうか、そういう話を聞いたり喋ったりするのが数学デー)。

「証明は滅びぬ、何度でもよみがえるさ」

とは言うものの(?)、自分で見つけた命題の証明は忘れないように残しておきたいものです。ということで、ある日僕が数学デーに持ち込んだバルス…じゃなくてパズルのお話です。

L型トロミノ並べ放題?

図のように正方形を3つ連結させてできる図形について考えます。

f:id:corollary2525:20190909224333p:plain

後で調べたら、この図形はL型トロミノ(L-tromino)と呼ばれるそうです*1なんか美味しそう。

この図形を2倍したものは元の図形でタイリングができます。

f:id:corollary2525:20190909224445p:plain


L型トロミノの大きさを(2倍せずに)固定して「大きさ1/2のL型トロミノで分割できる」と考えても構いません(むしろこっちの方が一般的?)。このように、「自身を自身と相似な図形で分割できる図形」をレプタイル(rep-tile)といいます。



ところで、ふと思ったんですけど…3倍した図形でも元の図形でタイリングできるんですかね?

f:id:corollary2525:20190909224457p:plain

よかったら考えてみてください。









実は…!









f:id:corollary2525:20190909224508p:plain

タイリングできるのかー。知らんかった。



じゃあ、4倍した図形ではどうなんでしょう?



ここで仮に、一辺の長さがnの正方形3つでできたL型トロミノを「大きさnのL型トロミノ」と呼ぶことにします。

大きさ4のL型トロミノは、少し工夫することで、大きさ1のL型トロミノでタイリングできることが分かります。

f:id:corollary2525:20190909224542p:plain

このタイリングは、まず大きさ4のL型トロミノを「大きさ2のL型トロミノを2倍した図形」だと思って分割します(実線)。すると、残り4個の図形は大きさ2のL型トロミノなので、タイリングが再利用できます(点線)。



この考え方を応用すれば、大きさ6のL型トロミノがタイリングできることも簡単に証明できますね。「大きさ3のL型トロミノを2倍した図形」だと思って分割し、残った4個の大きさ3のL型トロミノは、さっきタイリングできることを示したので、再利用すればいいのです。



ということは、奇数(あるいは素数)の大きさのL型トロミノがタイリングできることを証明さえできれば、すべての大きさのL型トロミノが大きさ1のL型トロミノでタイリングできることが証明できますね!

自分で見つけた成り立ちそうな定理を証明するの、わくわくします。

L型トロミノの性質とその証明

これから証明する定理を正確に述べます。

定理
すべての自然数nに対して,大きさnのL型トロミノは大きさ1のL型トロミノでタイリングできる.
ちなみに、レプタイルの用語で言い直すと「すべての自然数nに対して,L型トロミノは rep-n^2 であるn^2個の自身と相似な図形で分割できる)」となります。

「これ、証明できるんですかね?」
「知らんけどとりあえずn=7でやってみるか」
みたいなことを数学デーで話してたと思います。

で、皆さんと色々議論しながら、無事証明することができました。ありがとうございました。



証明には数学的帰納法を使いますが、今回は次のような形で使います:

P(n)自然数nに関する命題としたとき,

  1. P(1)P(2)P(3)が正しい
  2. n\geqq 4に対して,P(1)P(2)\cdotsP(n-1)がすべて正しいと仮定すると,P(n)も正しい

の2つを証明すれば,すべての自然数nに対してP(n)は正しい。

n=3まで正しいことを確認しなければならない所が今回のポイントです。そこに注目して証明をご覧ください。



証明
「大きさnのL型トロミノは大きさ1のL型トロミノでタイリングできる」という命題をP(n)とおきます.

[1] P(1)が正しいことは明らかで,P(2)P(3)が正しいことはすでに証明しました.

[2] n\geqq 4に対して,P(1)P(2),…,P(n-1)が正しいことを仮定して,

f:id:corollary2525:20190909224557p:plain

が大きさ1のL型トロミノでタイリングできること(つまりP(n)が正しいこと)を示します.


nが偶数のとき
n=2kk自然数)と表すと,次のようなタイリングができます:

f:id:corollary2525:20190909224608p:plain

ここで,大きさkのL型トロミノが4つありますが,1\leqq k< nであるから仮定より大きさkのL型トロミノは大きさ1のL型トロミノでタイリングできます.全体をみれば,大きさnのL型トロミノは大きさ1の図形でタイリングできることになります.

よって,nが偶数のときはP(n)は正しい.



nが奇数のとき
2nは偶数であるから,まずはこのように隙間なく埋められます:

f:id:corollary2525: 20190909224628p:plain

ここで,n\geqq 4であるからn-3>0.つまり,上図に記した長さn-3の線分がまだ存在することに注意します.

しかし,nは奇数なのでn-3は偶数です.したがって次のように隙間なく埋められます:

f:id:corollary2525: 20190909224641p:plain

埋めていない部分の図形に注目すると,これは大きさn-3のL型トロミノですね.

f:id:corollary2525: 20190909224652p:plain

仮定より,埋めていない部分の図形は大きさ1のL型トロミノでタイリングできます.

よって,nが奇数のときでもP(n)は正しい.


[1][2]より,すべての自然数 nに対してP(n)は正しい.■



数学的帰納法とパズル的アイデアのあわせ技、面白かったです!

To be continued...?

無事に証明ができたので、この後僕は数学デー終了まで「ゆるくベーシック圏論を読む会」の方で活動してました(今、最終章を読んでるんでこっちもアツいんです)。

数学デー終了後、僕はいつものようにTwitterで #数学デーinN高 を見てたんですけど…

他のレプタイルでも証明されてる!?

なるほど、とりあえず

■■
■■
型の図形も、同じ証明が適応できるみたいですね!興味深いです。同じ証明が適用できるレプタイルとできないレプタイルには共通な性質があったりするのかな?この続きは数学デーで話してみよう。

thank Q for rEaDing.φ(・▽・ )

*1:2個ならドミノ(domino)、3個ならトロミノ(tromino)、4個ならテトロミノ(tetromino)、一般にn個の正方形でできたポリオミノをn-オミノと言います。