円の中に距離を離して点を打つ問題

質問

直径10ｋｍの円の中に、どの点からも最低1ｋｍ離して点を打つとして、最大でいくつの点を打てるのでしょうか？

回答No.10

stomachman · ベストアンサー

ご質問は、「直径11kmの円の中に直径1kmの円がいくつ入るか」、つまり、「半径1の円の中に半径1/11の円がいくつ入るか」と言い換えられます。で、

http://hydra.nat.uni-magdeburg.de/packing/cci/d9.html
http://hydra.nat.uni-magdeburg.de/packing/cci/pdf/d9.pdf　　(pdf版)

は「半径1の円の中にN個詰め込める円の半径(radius)」の、これまで知られている最大値 r(N)と、その詰め込み方の一覧表、という資料です。これによれば

　　r(98)=0.0910… ＞ 1/11=0.0909… ＞ r(99)=0.0906…

なので、最大98個入るということのようです。

お礼

回答ありがとうございます。
"これまで知られている"ということは、それ以上の可能性もあるということですか。
しかし規則的な解法も無さそうですし、この辺りが限界のようですね。

回答No.9

momordica

気になってたので、実際に少し試してみたら９６個までは入りました。
結局、試行錯誤してみるしかないみたいですね。

基本方針は＃７さんと同じですが、間の詰め方を工夫することで、＃７さんの想定した
円よりもやや外側に配置していくことができるので、いくつかの列には概算値より
１つ余計に押し込むことができます。
ということで、内側から順に、
　1+7+13+19+25+31=96
この辺りが限界のような気がします。

お礼

回答ありがとうございます。
距離が固定でないから隙間の詰め方が問題みたいですね。
似たような問題が検索しても出てこないのは試行錯誤以外に解法が無かったからなのかもしれません。

回答No.8

okormazd

#7です。
直径4kmの円周が、12.6kmほどで、直径6kmの円周が18.8kmなので、この2つの円周の間に、1つ入るようなので、全部で、94個になるか。

お礼

回答ありがとうございます。
外から攻める方法ですね。

回答No.7

okormazd

1.
直径をDとすればD=10ｋｍの円周は、πD=31.4km以上だから、円周上に中心があり、重ならないように直径1kmの円を置けば、2つの小円の間隔は1kmだから、31個置ける。
2.
この内側に直径8kmの円を描いて、その円周上に小円を並べれば、πD=25.1kmだから、25個おける。
3.
同様に直径6kmの円ではπD=18.8kmで、18個置ける。
4.
直径4kmで、12個、直径2kmで6個置ける。
5.
中心に1個置けるので、
6.全部で93個置けるのではないか。

お礼

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

回答No.6

momordica

難しいですね。
少なくとも、＃４さんの回答の91個は最大ではありません。

＃4さんの図の６角形の外周に並ぶ30この円を取り除いて、代わりに
直径1の円を、直径10の円周上に中心を持ち、かつ互いに接するように
並べていくと、31個並べることができます。
また、外周の30個を除く61個の点はどれも外周の円周からは1以上
離れているので、新たに置いた31個の円がこれらと重なることもありません。

なお、外周上の点を含むのかどうかが問題視されていますが、上記の
ように並べた31個の円は、少しずらして中心が外周の円よりわずかに内側に
入るように置くことも可能なので、この場合、問題になりません。

したがって、少なくとも92個は置くことができます。
配置を最適化することで、さらに多くおける可能性もあるように思います。

お礼

回答ありがとうございます。
すっきりするような解法があるのかもしれないと思って質問させて頂いたのですが、そうもいかないようですね。

回答No.5

rnakamra

#2のものです。
こちらでも実際に作図して確認してみました。

#4の図を同じ図を書いたのですが、よく見るともう少し数を増やせそうな感じです。
図にある大きな円を右斜め上45°の方向にずらします。
大きな円が左下隅の小さな円の左上の円の中心にかかるところまで移動すると、どうやら1個増えそうな感じです。
この移動で4個外に出ますが、新たに5個の円の中心が大きな円の内部になりそうです。
厳密には確認していないけど。

お礼

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

回答No.4

DJ-Potato

感覚的には、こういう感じですかね。

お礼

回答ありがとうございます。
とても見やすい図をありがとうございます。ただ、最大なのかやはり疑問が残ります。

回答No.3

koujikuu

直径10Kmの円に内接する正六角形を一辺1Kmの正三角形で区切り頂点を数えれば良いと思いますが
私の計算では六角形の外周円には、一辺1Kmの正三角形は入らないですが、間違えたらすいません。

お礼

回答ありがとうございます。
正三角形だと計算がしやすそうですね。ただ、隙間が結構あるので本当に最大なのか分からないのです。

回答No.2

rnakamra

円の中に円周上が入るかどうかが問題になりそうです。
#1のおっしゃられるように直径10kmの円に対して、重ならないように直径1kmの円を中心が直径10kmの円内に収まるように配置する時の配置できる最大個数を考えればよいのです。
配置する小さい円の一部が円の外側になっていてもOK。中心さえ大きい円の中にあればよいのです。
簡単な配置としては、
1.大きい円の中心に1個中心が同じ点になるように小さい円を置く。
2.中心に置いた小さい円に密着するように小さい円を重ならないように置く。6個置けます。
3.さらにその外側に密着するように小さい円を配置。中心を結ぶと正六角形を描くように12個置けます。
4.これを繰り替えます。5重の正六角形ができます。

4.の一番外側にある円のうち一部の円の中心が大きい円の円周上になります。これを数えることができるかで答えが変わりそう。

お礼

回答ありがとうございます。
円周上に点を打つのもありです。

回答No.1

DIooggooID

直径10ｋｍの円の中に、「直径1ｋｍの円」を、どの円とも交わることなく配置した場合に、
何個の「直径1ｋｍの円」を描けるか、という見方をしてみてはいかがでしょう。

お礼

回答ありがとうございます。
視覚的（感覚的）にこれくらいの数になるというのは分かるのですが、その数が最大であるかどうかが分からないのです。