13×13の正方形に直径1の円を敷き詰める

少し前に同様な質問をしました。

13×13の正方形に直径1の円を重ならないように
なるべく多く描いたら何個できるか、という問題です。

以前に質問した時に教えていただいたような方法では
13の場合はうまくいかないようで
素直に13×13=169個とした方が多くなります。

ところが5×8の長方形には41個が可能なことから
41×4+3×3=173個の円はかけると考えたのですが
これより多く円をかくことはできるでしょうか?

No.1 ベストアンサー 回答者： ringohatimitu 回答日時： 2011/12/21 22:34

このタイプの問題はcircle packingと呼ばれるもので現段階では個別に調べていく方法しかないようです。

私はこの分野の素人ですが興味があったので調べてみると以下のサイトを見つけました：

http://hydra.nat.uni-magdeburg.de/packing/csq/cs …

これを参考にすると181個([表のradius]*2*13≒0.03848*26≒1.00048のときで、182個になると[表のradius]*2*13が1を下回ってしまう)が最良でしょうかね。

この回答へのお礼

回答ありがとうございました。
一番早く回答いただいたのでベストアンサーとさせていただきたいと思います。

お礼日時：2012/02/04 05:36

No.3 回答者： stomachman 回答日時： 2011/12/22 09:25

> 少し前に同様な質問

　http://oshiete.goo.ne.jp/qa/7200575.html のことですね。
　以前こういうのもありました→ http://oshiete.goo.ne.jp/qa/194307.html

　俵を積むように正三角形のパターンで9段積むと、その高さはANo.2の記号を使えば
　　h=d( ((√3)/2)(n-1) + 1)
に(d=1, n=9)を代入して7.9ほどになる。（ANo.2の式はミスプリでしょう。）
ここまでで
　　5×13 + 4×12 = 113個
残ったスペースに正方格子でまだ5段積めますから、
　　113+5×13 = 178個
は確実に入ることが分かります。このような「俵積みと正方形積みを切り替える方式」に限れば、俵9段正方形5段が最大であることは、上記の式を使って証明できます。俵10段だと正方形4段で177個、俵8段は最悪で正方形5段の166個しか入りません。

　しかし、ANo.1でご紹介のサイトのデータ(この表は感動ものですねー)によれば、既知の充填法で1x1の正方形の中に入れられる円盤の最大の半径(radius)は
　　181個で　0.038482824780
　　182個で　0.038417680974
　0.0384615385= (1/13)/2 はこの中間ですから、答は「これまで知られている最大は181個」ということ。図を見ると、異なる規則に支配される領域同士がせめぎ合っているようで面白い。その中間でうろうろしてる奴までいますね。パチンコ玉を四角い箱に投げ込んで振り回してみると案外簡単に再現できそうな気もします。（本当に入ると証明するのはとても面倒でしょうけれども。）

No.2 回答者： okormazd 回答日時： 2011/12/21 22:38

正方形に積み上げれば、

13×13=169
ですが、
正三角形に積み上げれば、
直径をd、段数をn、高さをhとすれば、
h=d(√(3)(n-1)+1)
で、
n=(h+d(√(3)-1)/(√(3)d)
です。
ここで、h=13、d=1とすれば、
n=14.85640646
となり、14段積めます。
13個が7段と12個が7段なので、全部で25×7=175個
でしょう。
ただし、1段分近く余ります。

この回答へのお礼

回答ありがとうございました。
EXCELで計算したときに、最上段が少なくなるパターンについて関数をミスしていました。
私も175の結果を出すことができました。

お礼日時：2011/12/22 09:27