[最密充填問題]
①一辺１００ｃｍの正方形に直径１ｃｍの円を重なりなく敷き詰めた場合、最大幾つ並ぶ？
②一辺１００ｃｍの立方体に直径１ｃｍの球を詰め込んだ場合、最大幾つ入る？
③一辺１００ｃｍの４次元立方体に直径１ｃｍの４次元球を詰め込んだ場合、最大幾つ入る？
回答は１つでも、２つでも、全部でも結構です。①は基本点、②はその２倍、③は基本点の３倍で計算し合計が得点です。
参考にならないかも知れませんが１辺２ｃｍとすると①ならば４つ、②ならば８つ、③ならば１７になると思います。がんばってください。
例によって、５日か６日目に開く予定です。ジョーク点と下駄（嵩上げ）点は内容をみて評価します。
No.7
204
48
57pt
*二次元：11444
普通に詰めると、下に100個並べ、その上に99個並べ、次に100個並べ、となって115段積み上げて、100を58段、99を57段の合計111443個になります。この場合上に0.273の隙間があきます。
この隙間を埋めるようなもっと高密度の充填があるかアニーリングでやってみましたが100x100の箱だと計算が重くて入るはずの111443個でも解を見つけられませんでした。
そこで10x10の箱でアニーリングしてみたら、以下のような配置が得られました。
通常なら下から10個、9個と積み上げて 10 9 10 9 10 9 10 9 10 9 10となり合計105個で上が0.340空きますが、途中で10 10 10になることで隙間を活用し1個余分に入ってます。高さは9.93です。
100x100の場合も同様に途中で100 100 100という段を入れれば一個余分の11444個入り、高さは 99.9948でギリギリです。アニーリングでもっとがんばれば別の方法でもっと入るかもしれませんが。
*三次元：1401611
普段FCC格子やHCP格子をいろんな角度で切り取って量子計算やってる人間なのでこれは非常に面白い問題です。
素直に二次元の拡張を考えると二次元の充填の上に同じ物をずらして重ねていけばいいです。下の図で黒が一番下、赤が次、青がその次です。
黒赤青黒赤青と重ねれば面心立方格子、黒赤黒赤と重ねればHCP格子になります。通常の充填率は同じですが箱に入れる場合は端での無駄が違うので、HCPの方が多く入ることになります。二次元の場合の11444個入るような場合は同じ厚さで積み重ねられないので考えないことにします。とりあえずHCPだと1389946個。
しかし面心立方格子は高校の科学の教科書に出てくるように四角っぽく積み重ねることができます。横の間隔はsqrt(2)/2で、71個並んで幅が1+sqrt(2)/2*140 = 99.9949493。いっぱいいっぱいです。個数は一段9941。次の段は9940。これを交互に71段と70段重ねると合計で1401611。高さも99.9949493。これで最適と思われます。
これを４５度回転すると一番下の段はちょうど100x100並ぶきれいな配置になりますが、全体の個数は1396070でさっきより減ります。領域は100x100x99.9949493。有効活用してますが偶数段の無駄が多い。
*四次元：175270410
FCC格子はn次元に拡張できて、n個の単位ベクトルv1, v2, .. vn を他との内積がすべて1/2になるように選び、i1~14を整数として i1 v1+ i2 v2 + i3 v3 + i4 v4 という点を生成すればよいです。
こうしてできる格子をいろいろな角度に傾いた100x100x100x100の箱で切り取って中に入る点が最大になるような箱を探します。互いに直行する i1 v1+ i2 v2 + i3 v3 + i4 v4という形のベクトルを４つ選んでこれを箱の方向とし入る点の数を数えるというのを低いミラー指数から力業で全検索すると、v1-v4, v2-v3, v1-v2-v3+v4, v1+v2+v3+v4という組の場合に一番いい結果が得られました。
具体的な配置は三次元で後の方の４５度回転したものを四次元方向第一段に、第二段は四次元座標 + sqrt(10)/4 の位置に第一段を (1/2, 0, sqrt(2)/4)だけずらしたものを置く（はみでる部分は消す）、３段めは１段めと同じ、４段めは２段目と同じ、の繰り返しを63回した配置です。四次元方向高さは99.821。最後の段を個数の少ない偶数段でなく奇数段にすると高さは100.03。おしい。ダメ。
結局個数は奇数段 100x100x71+99*99*70 = 1396070、偶数段 99x100x70 + 99x100x70 = 1386000で(1396070+1386000)*63=175270410。
別の方法として四次元方向の厚さはsqrt(10)/4で同じだけど、奇数段に３次元の前者の方 1401611個、偶数段はこれを(1/4,1/4,1/4)ずらして四次元方向sqrt(10)/4 に置く、というのを63回繰り返すと (1401611 + 1372000)*63 = 174737493 個に。奇数段はさっきより多いけど偶数段が少ないので全体でさっきより少ないです。
No.1
430
13pt
①10000
②1000000
③はわかりませんけどもしかして
1999702？
①②は格子状に並べた場合ですね。ならば③は100000000となるはずです。しかしモット詰まると思います。
No.2
50
38pt
①六方最密充填の１段目のみを上から見たような敷き詰め方が
最大数になるとして回答します。
まず正方形の下端部分に１００個円を敷き詰めます。
その上には９９個円に接する形で置けます。
その上は１００個ですね。
これをn段繰り返すと高さは1+(n-1)*(√3)/2です。
なぜなら、n段目の高さは1/2+[一辺が(n-1)の正三角形の垂線の足の長さ]+1/2だからです。
よってnの最大数は115です。
段数によって１００個入る行と９９個しか入らない行があるので
最大になるには１００個＊５８行＋９９個＊５７行で１１４４３個となります。
②六方最密充填が最大数になるとして回答します。
少し前に、六方最密充填よりも密な構造があると論文で見た気もしますが・・・
①と同様のプロセスで考えます。立方体の下端にまず①で出た最大数11443個を敷き詰めます。
次に、下端の隣り合う３つの球の上に１つの球を乗せるように２段目を作ります。
この４つの球の中心を結ぶと正四面体です。
２段目は①で考えた高さ（ここでは平面のｙ座標方向）としてはそのまま２段目に115段乗せると
(1+57√3)+((√3)-1)/2となり、100.015cm程度となり入りませんので、
114段になります。また①でいう１行（ｘ軸方向）に入る数も2段目では１つずつ少なく
なるので2段目の数は1443-100-114=11229個です。
これを繰り返すとn段目の高さは1+(n-1)*(√6)/3です。
なぜならn段目の高さは1/2+[一辺が(n-1)の正四面体の高さ]+1/2だからです。
底面の正三角形に垂線の足を引き交点を作り、重心と交点の距離をrとして
三平方の定理から導くやつです。
よってnの最大数は122となります。
つまり最大数は６１面＊１１４４３個＋６１面＊１１２２９個で１３８２９９２個となります。
③分かりません。
ベクトル以外で４次元なんて考えたことがありません。
同じように考えると
②の答えを使いながら
n段目の高さは1/2+[一辺が(n-1)の４次元の立体の、高さに該当するような何らかの体積]+1/2
になるのでしょうかね・・・。
①は私と同じ結果です、②私は1396046になりましたがNishidaTetsuoさんが正しいでしょう。③は19659601になるはずです（これは自信が有ります） 100＾4＋99＾4です 4次元になると球（超球と超球の間に丁度直径1つ分の隙間ができます。√4－１＝１
・・・9次元では隙間に2倍の直径の球（9次元球）が入れられます。
No.4
614
13pt
①１００×１００＝１００００ A１００００個
②１００×１００×１００＝１００００００ A１００００００個
③ちょっとわからないです・・・
間違ってるかもしれないのでよろしくお願いします。
あなたも、格子状配置ですね、ならばついでに③を100000000にしてもよさそうですが？、1番回答者のsotou_suzukiと同等ですね。
No.5
131
13pt
１は１００００ ２は１００００００
あなたも、格子状配置ですね、ならばついでに③を100000000にしてもよさそうですが？、1番回答者のsotou_suzukiと同等ですね。
No.6
8353
24pt
挑戦してみたいと思います!!
①直径1cmの円は普通の縦横1cmの正方形として考えました
この1㎠の正方形が縦横に100ずつ並べられますので
100^2=10000個
②これも直径1cmの球を縦横高さを1cmとした立方体として考えて
この1㎤の立方体が縦横高さ100ずつ並べられますので
100^3=1000000個
③これは流石に①.②のように単純ではありませんが
平方と立法の概念を考えて4次球は縦横高さにさらに別に
直角に伸びた値の立方体に直せる!?と考えて
縦横高さ4つ目の値で、できた1cm4の4次元立方体を
１辺100cmの４次元立方体に入れますので
100^4=100000000個
でもこれだと参考資料の③の１辺が2cmの場合は16が出てしまい
17に合わないので、その足りない要素を考えました
100÷2=50(単純すぎる)
そういう概念かなと想像して
100000000＋50=100000050個にします
という事は3cmの場合は半個という事になってしまう!?
あなたも、正方格子状配置ですね、、1番回答者のsotou_suzukiより少しすすんだようですね。
期待したのですが、①は蜂の巣 ②はダイヤモンドの結晶を思い出してもらえば・・・モット詰まるのは考え付くと思いますが。
あなたには、「期待」してたのですよ
No.7
20448
ここでベストアンサー
57pt
*二次元：11444
普通に詰めると、下に100個並べ、その上に99個並べ、次に100個並べ、となって115段積み上げて、100を58段、99を57段の合計111443個になります。この場合上に0.273の隙間があきます。
この隙間を埋めるようなもっと高密度の充填があるかアニーリングでやってみましたが100x100の箱だと計算が重くて入るはずの111443個でも解を見つけられませんでした。
そこで10x10の箱でアニーリングしてみたら、以下のような配置が得られました。
通常なら下から10個、9個と積み上げて 10 9 10 9 10 9 10 9 10 9 10となり合計105個で上が0.340空きますが、途中で10 10 10になることで隙間を活用し1個余分に入ってます。高さは9.93です。
100x100の場合も同様に途中で100 100 100という段を入れれば一個余分の11444個入り、高さは 99.9948でギリギリです。アニーリングでもっとがんばれば別の方法でもっと入るかもしれませんが。
*三次元：1401611
普段FCC格子やHCP格子をいろんな角度で切り取って量子計算やってる人間なのでこれは非常に面白い問題です。
素直に二次元の拡張を考えると二次元の充填の上に同じ物をずらして重ねていけばいいです。下の図で黒が一番下、赤が次、青がその次です。
黒赤青黒赤青と重ねれば面心立方格子、黒赤黒赤と重ねればHCP格子になります。通常の充填率は同じですが箱に入れる場合は端での無駄が違うので、HCPの方が多く入ることになります。二次元の場合の11444個入るような場合は同じ厚さで積み重ねられないので考えないことにします。とりあえずHCPだと1389946個。
しかし面心立方格子は高校の科学の教科書に出てくるように四角っぽく積み重ねることができます。横の間隔はsqrt(2)/2で、71個並んで幅が1+sqrt(2)/2*140 = 99.9949493。いっぱいいっぱいです。個数は一段9941。次の段は9940。これを交互に71段と70段重ねると合計で1401611。高さも99.9949493。これで最適と思われます。
これを４５度回転すると一番下の段はちょうど100x100並ぶきれいな配置になりますが、全体の個数は1396070でさっきより減ります。領域は100x100x99.9949493。有効活用してますが偶数段の無駄が多い。
*四次元：175270410
FCC格子はn次元に拡張できて、n個の単位ベクトルv1, v2, .. vn を他との内積がすべて1/2になるように選び、i1~14を整数として i1 v1+ i2 v2 + i3 v3 + i4 v4 という点を生成すればよいです。
こうしてできる格子をいろいろな角度に傾いた100x100x100x100の箱で切り取って中に入る点が最大になるような箱を探します。互いに直行する i1 v1+ i2 v2 + i3 v3 + i4 v4という形のベクトルを４つ選んでこれを箱の方向とし入る点の数を数えるというのを低いミラー指数から力業で全検索すると、v1-v4, v2-v3, v1-v2-v3+v4, v1+v2+v3+v4という組の場合に一番いい結果が得られました。
具体的な配置は三次元で後の方の４５度回転したものを四次元方向第一段に、第二段は四次元座標 + sqrt(10)/4 の位置に第一段を (1/2, 0, sqrt(2)/4)だけずらしたものを置く（はみでる部分は消す）、３段めは１段めと同じ、４段めは２段目と同じ、の繰り返しを63回した配置です。四次元方向高さは99.821。最後の段を個数の少ない偶数段でなく奇数段にすると高さは100.03。おしい。ダメ。
結局個数は奇数段 100x100x71+99*99*70 = 1396070、偶数段 99x100x70 + 99x100x70 = 1386000で(1396070+1386000)*63=175270410。
別の方法として四次元方向の厚さはsqrt(10)/4で同じだけど、奇数段に３次元の前者の方 1401611個、偶数段はこれを(1/4,1/4,1/4)ずらして四次元方向sqrt(10)/4 に置く、というのを63回繰り返すと (1401611 + 1372000)*63 = 174737493 個に。奇数段はさっきより多いけど偶数段が少ないので全体でさっきより少ないです。
さすがitaさん、分かりやすい図をありがとうございます。
①は私と同じ結果です、②私は1396046になりましたがNishidaTetsuoさんが正しいでしょう。③は19659601になるはずです（これは自信が有ります） 100＾4＋99＾4です 4次元になると球（超球と超球の間に丁度直径1つ分の隙間ができます。√4－１＝１
・・・9次元では隙間に2倍の直径の球（9次元球）が入れられます。
①は私と同じ結果です、
②私は1396046になりましたがNishidaTetsuoさんが1382992、itaさんはそれより多い答えを出してもらいました、確認します。
③は19659601になるはずです（これは自信が有ります） 100＾4＋99＾4です 4次元になると球（超球と超球の間に丁度直径1つ分の隙間ができます。√4－１＝１ がみそ。
・・・9次元では隙間に2倍の直径の球（9次元球）が入れられます。・・・同じ直径の球（9次元球）が幾つ入るかは計算してません。
No.8
767128
12pt
まず①です。
http://soudan1.biglobe.ne.jp/qa5496955.html
のANo.3の人が回答されているように11443個です。
段数 並ぶ個数 円の中心のＹ座標
１ １００ ０．５
２ ９９ ０．５＋√３×０．５＝１．３６６０２５
・
・
１１５ １００ ９９．２２６９０
１１６段目は９９．５を超えるのでダメ。
で総計は（１００＋９９）×５７＋１００＝１１４４３個
並べるのを四隅から初めて真ん中に隙間を残しても、１１４４４個目は入らないことは確認。
折角URLまで付けていただいているのに ②s=(70+1)*(4*70^2+2*70+1)=1401611個の書いていただければよかったのに。
No.9
767128
39pt
次に②は、１３８９９４６個
http://soudan1.biglobe.ne.jp/qa5496955.html
のANo.3の人が回答されている1,315,945個よりかなり多い。
①で底面に１１４４３個並ぶ
２段目は、底面に並んだ玉の上に最密で並べていくと
http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%A...
１列目１００、２列目９９、・・・１１４列目９９、で１１５列より１列少なく終了
２段目に並んだ個数は底辺より１００個少ない、１１３４３個
１段目と２段目の高さの差は、正四面体の高さの法則から
http://ja.wikipedia.org/wiki/%E6%AD%A3%E5%9B%9B%E9%9D%A2%E4%BD%9...
√（２／３）
①と同様に
段数 並ぶ個数 球の中心のＹ座標
１ １１４４３ ０．５
２ １１３４３ ０．５＋√（２／３）＝１．３１６５０
・
・
１２２ １１３４３ ９９．２９６０９
１２３段目は９９．５を超えるのでダメ。
で総計は（１１４４３＋１１３４３）×６１＝１３８９９４６
こっちは１３８９９４７個目が入らない保証なし。
http://ja.wikipedia.org/wiki/%E7%90%83%E5%85%85%E5%A1%AB
から、最密の74.048%の充填率だとして限界値を出すと、１４１４２１２個なので
まあまあのセン行ってるかな。
②はかなり、皆さん近い（正解に近いというのでなく、値が近いという意味）答えになってますね。いい加減ですが、正解が分からなくなってきました。
No.10
20448
31pt
四次元間違えました！例題ちゃんと読めばよかった。
立方格子にして隙間にも入れればいいんですね。
100^4+99^4=196059601
この論文でも四次元ではこれが最密らしいと書いてあります
さすが、見抜かれたか！！
No.11
140
21pt
1.100×100=10000個
2.高さ1cmの合間に100個と81個の球体の並び方を考えて
181×100^2=1810000 球の高さの関係でこれでは入らないので0.7をかけて
=1267000
3.世次元の場合表わせる体積の方はxyzu
1辺が100cmのため四次元立方体は100^4=100000000
超球の体積がπ^2 r^4 /2=4.934
もし仮に四次元空間に隙間なくうまったとすれば
10000000/4.934=20267531.41
少数切り上げ=20267531
①②はまあいいとして③はやはり分かりにくかったですか？
何も、四次元球の体積で割る必要は無かったのでは、1億は入れ物の容量であって（1000万に間違っておられるようですが）、また超球の超体積は1より小さいですよ（直径が1ですから） 計算間違いというより、算出の考え方が違っている・・・という事で（itaさんの考えが正しいです）
やまだまや（真優）
2011/02/26 13:07:27
1
1
1
1
2
66
64
きゃづみぃ
サディア・ラボン
ニャンざぶろう
ita
八咫烏
さすがitaさん、分かりやすい図をありがとうございます。
①は私と同じ結果です、②私は1396046になりましたがNishidaTetsuoさんが正しいでしょう。③は19659601になるはずです（これは自信が有ります） 100＾4＋99＾4です 4次元になると球（超球と超球の間に丁度直径1つ分の隙間ができます。√4－１＝１
・・・9次元では隙間に2倍の直径の球（9次元球）が入れられます。
①は私と同じ結果です、
②私は1396046になりましたがNishidaTetsuoさんが1382992、itaさんはそれより多い答えを出してもらいました、確認します。
③は19659601になるはずです（これは自信が有ります） 100＾4＋99＾4です 4次元になると球（超球と超球の間に丁度直径1つ分の隙間ができます。√4－１＝１ がみそ。
・・・9次元では隙間に2倍の直径の球（9次元球）が入れられます。・・・同じ直径の球（9次元球）が幾つ入るかは計算してません。