正方形の詰め込み問題について考えましょう。次のような問題です。私がこの問題を初めて見たのはマーチン・ガードナーの「数学ゲームIV」です。
「同じ大きさのn個の正方形を、それより大きい、なるべく小さな面積の正方形の中へ、互いに重なりあわないように入れよ」(「数学ゲームIV」より)
という問題です。
n個の正方形の一辺の長さを1として、枠になる正方形の最小値がいくらになるか考えてください。
nが平方数の場合は明らかに隙間なく詰め込めるので、最小値はその平方根となることはすぐにわかります。
n=5までだと下のような詰め込みがあります。（n=1は省略）
n=10だとこんなの
さらにn=11だとこんなの！？
これらの詰め込みは適当に端から詰め込んでいったものよりも枠の正方形のサイズが小さくなっています。
対称性が崩れちゃうのがポイントで、これを見るとこの問題の難しさがわかります。
これらが枠のサイズが最小となっているかが問題ですね。
ガードナーの本の時点では、nが2,3,5と平方数の場合を除いて未解決となっています。
つまりほとんどの場合未解決だったようですが、今はどうなんでしょう？
他のnの場合の詰め方の例は調べれば色々出てきますが、便利なのはWolframAlphaに「正方形に〇個の正方形を詰める」と入力する方法です。すると、その個数の詰め方を表示してくれます。
順に試してみるとn=51を除いてn≦100の場合まで詰め込みの例が出てきました。
でも、これは何を元にしているのでしょうか？
最小と証明されたもの？それとも知られている最良の詰め方？
このへんはよく分かりませんでした。困った。
「出典情報」の所にいくつか論文やサイトが載っているので、ザっと見てみたんですが、どれも円を詰め込む問題を扱っているっぽいんですよねー。
結局よくわかりません、ごめんなさい。
もうちょっと調べてみると、Erich Friedmanという方の書かれたこちら、またはこちらのサイトがとても詳しそうです。詳しく知りたかったら自分で読んでね。
まあとにかく、この問題は賢い人に任せて、違うことを考えましょう。
ここからは、今までにも何回か扱ったアンチスライドという条件を追加しましょう！
問題
「同じ大きさのn個の正方形を、それより大きい、なるべく小さな面積の正方形の中へ、互いに重なりあわないように、かつアンチスライドに入れよ」
つまり、全ての正方形が固定されて動かないような詰め方を考えます。
上にあるようなn=１～５の場合の詰め方だとn=2, 3の場合は正方形がスライドしちゃうスペースができているので、こうゆうのはNGです。
n=5の場合はスライドしないのでOKです。
上にあるn=10の詰め方はダメだけどn=11はOKです。
少し考えるとn=2,3の場合は次のような詰め方がありますね。
図の下に書いてあるのは一辺の長さです。計算は難しくないので省略。
最小かどうかの証明は難しいので、とりあえずアンチスライドになる詰め込みを見つけていきましょうか。
とりあえずWolflamAlphaにあるn=100までの場合の詰め方でアンチスライドになっているものを探してみましょう。
平方数を除くとn=5,11,40だけです。
かなり少ないですから、考える余地がたくさんありますね。
n=40
他のnについても探していきたい所ですが、やってみるとだいぶ難しいですねこれ。
そもそも、全てのnに対して必ずアンチスライドな詰め込みが存在するのでしょうか？
このへんも含めて、次回に続きを考えましょう。