箱に瓶を詰める問題

コンビニでビンを陳列している時に思いつきましたが
どうやって解くか全くわかりません。
有名な問題でしたらサイトや名前をお教えください。

縦・横の長さがそれぞれx,yの長方形に
半径1の円をなるべく多く敷き詰めることを考えます。

m,nを自然数として
x=mかつy=nならば敷き詰められる円の個数はmnであってますか?
次にx=mのまま、yのみを(n+d)に拡大したとき、敷き詰められる円の個数がmnを超えるような最小の実数dはいくつですか?
(そんな陳列は汚くて店長に怒られそうですが)

No.4 ベストアンサー 回答者： FT56F001 回答日時： 2011/12/20 21:08

>x=mかつy=nならば敷き詰められる円の個数はmnであってますか?

もっと入ると思います。

横8，縦5とします。下の詰め方では8*5=40個しか入りませんが，
上の詰め方では41個入ります。
横の必要長は，(1/2)+8*(√3/2)+(1/2)=7.928で8より小さいです。

この回答への補足

回答ありがとうございます。
mとnを用いて一般化したような式はあるのでしょうか?
ガウス記号とか出てきそうですが。

補足日時：2011/12/20 21:32

No.9 回答者： ferien 回答日時： 2011/12/21 03:31

最初の問題で、

>x=mのまま、yのみを(n+d)
と提示されていたので、
ｍは縦の個数、ｎは横の個数なのだと思っていました。
また、ｎに追加するｄの部分と言う意味で問題を捉えていました。
ｙ＝（ｍ－２）＋（１＋ルート３）のような関係を問題にしていたとは、説明されていなかったので
ｎが突然ｍ－２に変わったような印象です。
ｙ＝（ｍ－２）＋（１＋ルート３）の式について説明していただけたら、誤解することもなかったと思いますが。。
No.4さんの並べ方については、良く理解できたしなぜそのようにできるのか理由も分かりました。
非常に参考になりました。

この回答への補足

直径と半径の誤記や
文字の誤記が多かったことはお詫びいたします。
またy=(n-2)+1+√3の誤りです。

多くの方が質問の真意を理解なさっているのに
dが整数でないといけないと考えられた辺りや
拡大する以前も簡単にmnと判断される辺りから
失礼ですが、この問題には力不足かと思います。

何度も回答いただいたことには感謝いたします。

補足日時：2011/12/21 04:50

No.8 回答者： ferien 回答日時： 2011/12/20 23:29

申し訳ありません。

訂正です。

ｍ＝２のとき、ｄ＝(1/2)×２＋(ルート3/2）×２＝１＋ルート３

ｍ＝３のとき、ｄ＝(1/2)×２＋ルート3/2＝１＋ルート3/2　です。

よろしくお願いします。

この回答への補足

yとdを混同されていませんか?

補足日時：2011/12/21 01:42

No.7 回答者： ferien 回答日時： 2011/12/20 22:54

度々すみません。

>m=2のときですが
>2(m-2)個の円は今まで通り升目状に敷き詰め
>残りの場所に、サイコロの5のように円を入れます。
>すると2m+1個の円が入ります。
残りあと５個だけ詰めると言うことですか？理解できてなくて済みません。

>先ほどのはn=√3-1の誤りでした。
これでもやはり１より小さいので、無理だと思います。

No.4さんが回答して下さいましたが、

あの図のｍ＝２の場合を参考にしてみてはどうでしょう？　あの場合だと残り５個詰めるのであれば、
ｄ＝１＋ルート３で、３より短くできます。
ｍ＝３だと、ｄ＝(1/2)（１＋ルート３）で、1.36ぐらいなのでさらに短くできます。

円の中心の間隔が、１辺＝１の正三角形の高さ（＝ルート３／２）になっているので、短くできるようです。

このような問題を考えるのは初めてなので、非常に参考になりました。

この回答への補足

dを誤解されてませんか?
私よりあなたの方が4を参考にされるべきかと。

m=2のとき
y=(m-2)+(1+√3)だから
d=√3-1になります。

補足日時：2011/12/21 01:21

No.6 回答者： alice_44 回答日時： 2011/12/20 22:40

それは、「詰め込み問題」といって、たいへん難しい問題です。

x,y が円の直径に対して十分大きい場合には、蜂の巣状に置くのが最善
と知られていますが、比較的小さい x,y に対してどうなるかは、
誰も知らないのではないかと思います。明示的な配置の公式は、
ありそうもない としか言えません。
少なくとも、最大数が mn ではない ことだけは確実です。
一度、「際密充填」または「六方格子」で google してみて下さい。

この回答への補足

回答ありがとうございます。

升目状に並べる場合(つまり最大数がxyになる場合)と
互い違いに並べる場合との境界条件とかわかっているのでしょうか?

また、規則的でない並べ方が最密になることは無いのでしょうか?

補足日時：2011/12/21 01:28

この回答へのお礼

六方格子で調べると化学の空間的なものしか見つかりませんでした。
自分としては今回の問題は次元が少なくなって理解し易いかと思ったのですが難しいものですね。
化学の結晶の場合は粒子どうしの相互作用ですが
箱という形で外から押さえた場合にどうなるかは少し違いそうで面白そうです。

お礼日時：2011/12/21 05:01

No.5 回答者： asuncion 回答日時： 2011/12/20 21:11

縦・横の大きさや円の直径によっては、格子状に敷き詰めるよりも

たくさん詰められる場合があるようです。

例えば、５×８の長方形に直径１の円をできるだけたくさん置こうとするとき、
５×８＝４０
が最大ではなく、
５、４、５、４、５、４、５、４、５
と敷き詰めた４１が最大になるようです。数学的な証明はできませんが。

なんとなく、格子状だとすき間が大きいような感じはしますけどね。

この回答への補足

回答ありがとうございます。
ジュース缶などを入れる段ボール箱は
確か6×4だったと思いますが
意味はありそうですね。

正方形の方が段ボールの原料費は少ないでしょうが
こういった現象は起こりやすい気もします。

補足日時：2011/12/20 21:21

No.3 回答者： ferien 回答日時： 2011/12/20 20:33

度々失礼します。

>補足の補足です。
>m=1のときd=1
>m=2のときd=√2-1
>かと思いますが
>m=3のときd<√2-1のものが存在しますか?

これを見ただけでは分からないので、できればどのように考えたのか教えて下さい。
ｄは最低１でないと１個も増やすことはできません。（実際はもう少し長めの方がいいと思いますが）

>m=1のときd=1
の場合しか成り立たないのでは？

この回答への補足

たびたびありがとうございます。

m=2のときですが
2(m-2)個の円は今まで通り升目状に敷き詰め
残りの場所に、サイコロの5のように円を入れます。
すると2m+1個の円が入ります。
先ほどのはn=√3-1の誤りでした。

補足日時：2011/12/20 20:52

No.2 回答者： ferien 回答日時： 2011/12/20 20:14

>半径1でなく直径1の誤りでした。

>解答の前半についてですが
>m,nがともに偶数でないと成り立たないような気がします。

直径２の場合は、偶数でなければならないと思います。
直径1だったら気にしなくてもいいですね。

>後半の意味がよくわかりません。
>0<d≦1であることは確かだと思いますが…。

ｙの長さ全体に制限がある場合は、ｎ＋ｄのｄの値を確定できますが、
yのみを(n+d)に拡大しただけでは、ｄの値は決められないと言うことです。

普通こういう場合は、なるべく多くの個数を詰めたいからｄの最大値を考えるほうがいいと思いますが。
また、ｄも実数ではなく自然数として考えた方がいいと思います。
ｙをｄだけ拡大すると、あとｎｄ個さらに詰めることができます。

No.1 回答者： ferien 回答日時： 2011/12/20 19:17

縦・横の長さがそれぞれx,yの長方形に

半径1の円をなるべく多く敷き詰めることを考えます。

>m,nを自然数として
>x=mかつy=nならば敷き詰められる円の個数はmnであってますか?
直径が１であればｍｎ個だと思いますが、半径が１であれば直径が２なので、
縦にm/2個、横にn/2個しか詰められないので、m/2×n/2＝mn/4個

>次にx=mのまま、yのみを(n+d)に拡大したとき、敷き詰められる円の個数がmnを超えるような最小の実>>数dはいくつですか?
ｙをいくらでも大きくできるのであればいくらでも詰められるから、最小値を考える必要がないのでは？と思います。ｙに制限があれば、最小値を考える必要があります。

この回答への補足

解答ありがとうございます。
半径1でなく直径1の誤りでした。

解答の前半についてですが
m,nがともに偶数でないと成り立たないような気がします。

後半の意味がよくわかりません。
0<d≦1であることは確かだと思いますが…。

補足日時：2011/12/20 19:32

この回答へのお礼

補足の補足です。
m=1のときd=1
m=2のときd=√2-1
かと思いますが
m=3のときd<√2-1のものが存在しますか?

お礼日時：2011/12/20 19:46