ルジンの問題とは
「正方形を大きさの異なる正方形に分割する」
という問題で、モスクワ大教授のルジンがこの問題を提起しました。
この問題に関するあれこれは他で調べればすぐにわかるのでここでは書かないことにして、いきなり答えを書くとこんな感じ。
数字は各正方形の辺の長さを表しています。大きな正方形が大きさの異なる21個の正方形に分割されていますね。
もうちょっと詳しい用語を付け加えると、
内部に長方形の部分を含まないものを単純型、そうでないものを複合型といいます
また内部の正方形の辺の長さが全て異なるものを完全型、そうでないものを不完全型といいます。
例えば複合型とはこんな感じ。
下部中央に長さ2の正方形2つで長方形を作っていますよね。
しかも同じ大きさの正方形を含んでいますので、これは複合型不完全正方分割正方形です。
まずみんな気になるのが、単純で完全な正方分割は存在するのか？存在するなら必要な内部正方形の数(分割数)の最小はいくつか？という問題ですね。
その答えが最初の図というわけで、デゥイベスチジンという方によるものです。
この21個の正方形への分割が最小であるということも示されているみたいです。
この解が発見されるまでに、単純型だけど不完全型だったり、完全型だけど複合型だったり、単純型で完全だけど長方形であるような解が見つけられ、最終的に単純完全正方分割正方形が発見されてこの問題は解決されたというわけです。
これはずいぶんと古い問題なんですが、でもまだまだ色んな問題が考えられそうですね。
では逆に制限のゆるい複合型不完全正方分割正方形を考えてみたいと思います。
つまり内部に長方形の部分があってもいいし、同じ大きさの内部正方形があってもいいということです。
この条件でいかに少ない種類で、いかに少ない枚数で分割できるか考えてみましょう。
だってそうでしょう。
正方形のタイルで床なり壁なりを埋め尽くしたいなーと思った時、同じ大きさのタイルをまとめて発注したほうが良いですよね？
デゥイベスチジンみたいに21種類の大きさのタイルを注文したりしたら迷惑ですよ。
てことで正方形をk種類の正方形を用いて分割する時の分割数の最小値n(k)をちょっと考えてみました。
k=1の場合
n(k)=1
当たり前です。ちなみに単純型完全正方分割正方形です。
k=2の場合
6が最小かな？
最小かどうかの証明はしていません。とりあえずn(2)≦6です。
2種類のタイルで埋め尽くしたいなーと思った時はとりあえず6枚買ってくれば十分です。
k=3の場合
8が最小？
n(3)≦8はいえます。
k=4の場合
この辺から難しそうです。
4種で9枚が見つけた中では最小です。
てことでn(4)≦9
同様の方法で分割を考えていくと
5種10枚でn(5)≦10
6種11枚でn(6)≦11
7種12枚でn(7)≦12
この感じだとn(k)≦k+5で分割できそうな雰囲気ですね。
本当に一般のkで出来るかは確かめていませんが、仮にこの調子で行ったとして問題はk=21ですよね。
最初にあげた単純型完全正方分割正方形があるので、n(21)=21になることは既にわかっています。
この例が最小の単純型完全正方分割正方形であるので、k=1は特別として除くと、2≦k≦20の場合はn(k)=kは成り立たないわけです。
さあ、この20と21の差は何なのでしょうか？
21になると何が変わるのでしょうか？
とても気になります。何かあるんでしょうか。とても難しいですね。
ちなみに単純完全型の例がいくつか知られていますので、そこから
n(22)=22、n(25)=25、n(26)=26、n(38)=38、n(55)=55となることがわかっています。
他にどれぐらいあるのかは知りませんが、これらの数字は何か特別な意味を持っているんでしょうか？
今日の考察は終わりです。問題をまとめましょう
①n(k)≦k+5はk≧8でもいつも成り立つのか？
②3≦k≦20ではn(k)=k+5が最小なのか？
(より少ない分割を見つける or 最小であることを証明する)
③20と21のn(k)の違いはどこから産まれるのか？
④n(k)=kを満たす21、22、25、26、38、55といった数字は何が特別なのでしょう？意味のある数字なのでしょうか？