一辺が10mの正方形の部屋の中に、n人の人間がいる。 このn人が、互いにできる限り距離をとろうとしているとき、 n人の最善の配置を考え、その距離を答えなさい。
n=2,3,4までは簡単なのですが、5以上がさっぱりです。
|
No.86718 - 2023/11/14(Tue) 22:15:37
| ☆ Re: ソーシャル・ディスタンス問題 / IT | | | 最善の配置 かどうかは、どうやって評価するのですか? 最短距離が最大とか?
n=5 のときは、一辺が5mの正方形4つに分割して考えれば良いのでは?
|
No.86719 - 2023/11/14(Tue) 22:25:17 |
| ☆ Re: ソーシャル・ディスタンス問題 / らすかる | | | No.86720 - 2023/11/15(Wed) 00:41:26 |
| ☆ Re: ソーシャル・ディスタンス問題 / 浅野 | | | > 最善の配置 かどうかは、どうやって評価するのですか? > 最短距離が最大とか? > > n=5 のときは、一辺が5mの正方形4つに分割して考えれば良いのでは? 「最善の配置」は、おっしゃる通り、人間同士の距離の最短距離の最大値で考えています。
|
No.86725 - 2023/11/15(Wed) 22:20:27 |
| ☆ Re: ソーシャル・ディスタンス問題 / 浅野 | | | > n=3はどうなりましたか?
n=3のときは、正方形をO(0,0),A(10,0),B(10,10),C(0,10)としたとき、1人をOに固定し、後の2人をAB上とBC上に置き、正三角形ができる配置を最大と考えました。
|
No.86726 - 2023/11/15(Wed) 22:23:19 |
| ☆ Re: ソーシャル・ディスタンス問題 / らすかる | | | 回答ありがとうございます。 で、n=5の場合はITさんのヒントでわかりましたか?
|
No.86727 - 2023/11/15(Wed) 22:56:01 |
| ☆ Re: ソーシャル・ディスタンス問題 / 浅野 | | | わかりました。 (0,0),(10,0),(10,10),(0,10),(5,5)に 配置すればいいんですね。 n=6以上が難しそうですね。
一般化なんて夢のまた夢です
|
No.86730 - 2023/11/16(Thu) 19:26:44 |
| ☆ Re: ソーシャル・ディスタンス問題 / らすかる | | | n=6の場合は (0,0),(10,0),(5,10/3),(0,20/3),(10,20/3),(5,10) のように配置するのが良いようです。 n=20ぐらいまでの解はわかりますが、一般化は無理だと思います。
|
No.86731 - 2023/11/16(Thu) 21:27:41 |
| ☆ Re: ソーシャル・ディスタンス問題 / 浅野 | | | n=6のときは、n=3のときの正三角形の各辺から垂直二等分線を引いて、それと外郭の正方形との交点が最適な位置になると思っていましたが、違いますか?
n=20まですぐ出るなんて。すごいです。 何かコツがありますか?
|
No.86732 - 2023/11/18(Sat) 00:03:48 |
| ☆ Re: ソーシャル・ディスタンス問題 / らすかる | | | > n=6のときは、n=3のときの正三角形の各辺から垂直二等分線を引いて、それと外郭の正方形との交点が最適な位置になると思っていましたが、違いますか? 違います。それだと最短距離が5(√6-√2)≒5.176になりますよね。 私が書いた座標にすると最短距離が5√13/3≒6.009となり、より長くなります。
> 何かコツがありますか? いろいろネット検索して正解を見つけるのがコツです。
|
No.86733 - 2023/11/18(Sat) 01:32:30 |
| ☆ Re: ソーシャル・ディスタンス問題 / 浅野 | | | >いろいろネット検索して正解を見つけるのがコツです。 ネットに同じような問題があるんですか? 私も検索はしてみたんですが、見つからず、知りませんでした。 どんなワードで検索されたんですか?
|
No.86757 - 2023/11/19(Sun) 19:33:50 |
| ☆ Re: ソーシャル・ディスタンス問題 / らすかる | | | 「点を配置する」ものがあるかどうかはわかりませんが、正方形を大きくすれば 「円を正方形に詰め込む」問題と同様になります。 「詰め込み」はpacking、「円」はcircle、「正方形」はsquareなので 例えば「packing circle in square」のように検索すると ↓このページが見つかります。 https://en.wikipedia.org/wiki/Circle_packing_in_a_square ここにn=20までの図があり、表のdnの値を10倍したものが 今回の問題の答えになります。 この図を見るとわかるように、例えばn=10などは一見きれいに見える図ですが 上の2個と右の3個を除いたサイコロの目のような配置の5個は上の2個のy座標が微妙に 異なるなど、かなり複雑な配置になっています。(n=10のdnの値は 18次方程式の解らしいです。)ここらへんが「一般化は無理」と思う理由です。
|
No.86761 - 2023/11/19(Sun) 20:36:10 |
|