自作問題(図形？)です

Question

自分で考えた問題なんで、解けるかどうかも分かりません

「１辺70cmの正方形の内部(辺上含む)に、50個の点を適当にばらまく。このとき、２点間の距離がαcm以下になるような２点が必ず存在する。」
上記の主張が成り立つようなαの最小値を求めよ。

これの元ネタは、αでなく10√2 という具体的な値で、これが成り立つことを証明せよというものです。
この場合は、正方形を7×7=49個の小正方形に分けると、鳩の巣原理によって明らか、ということでした。
しかし、直感的に、これより小さな値でも成り立ちそうなので、この問題を考えました。
作ったはいいものの、私には解けそうにありません。
誰か代わりに解いてやってくれませんか？
できれば、高校レベルの知識で分かるように説明してほしいと思います。

stomachman · Accepted Answer

またまたstomachmanです。
No.4のlinus3030さんによるアイデアを使って、αminの上限をさらに絞り込んでみましょう。

　直径１のコインのたわら積みでぎっしり平面を埋め尽くした状態を考えます。（これが最密充填であることは自明として認めることにします。）するとコイン１個あたり、一辺１の正三角形２個分の面積、すなわち√3/2を必要とします。
　では、正方形でこの平面を切り取った時、その中にコインは幾つ入るか。
　正方形の辺や角の部分ではコインが半端に切り取られ、これらは数に入らない。だから、「コインの個数は(正方形の面積×2/√3)を越えることはない」と言えます。この事から、50個のコインを入れられる正方形の面積は、(25√3)以上なくてはならないことが分かります。

　一方、コインをどう並べても、正方形の４つの隅の部分をコインが覆うことはあり得ません。ちょっと余ってしまう。その余る部分の面積は（1-コインの面積）に等しい。だから正方形内部のうち有効に使える部分の面積は、「正方形の面積-(1-コインの面積)」です。
　ゆえに50個のコインが入れられる正方形は、
(正方形の面積)-(1-コインの面積)＞25√3
を満たさねばなりません。すなわち
(正方形の面積)＞25√3+(1-π/4)
よってその正方形の一辺は
√(25√3+(1-π/4))≒6.597
よりも大きくなくてはならない。以上から、
αmin＜70/(√(25√3+(1-π/4))-1)≒12.507
という、さらに改良されたαminの上限が得られました。

　ここから先、上限を抑えていくには、辺や角の近くでの余りの出方などを細かく詰めていく必要があるから、かなり難しいでしょう。

　一方、下限の方は、実際にパチンコ玉などを並べて四角い枠で囲んで揺すってみることで、ひょっとすると旨い配置が見つかるかも知れません。もし見つかったら、きちんと計算して正方形の大きさを出せば下限が改良できます。
　とりあえず、No.8の最後で示した配置における正方形の一辺の長さL''を頑張って計算してみました。配置はこんな感じです。
　●　●　●　●　●　●　
　　○　●　●　●　●　●
　８　●　●　●　●　●
　　○　●　●　●　●　●
　●　●　●　●　●　●　
　　○　●　●　●　●　●
　８　●　●　●　●　●　
　　○　●　●　●　●　●
8のところに縦に２個くっついたコインが入ります。これらの左側に縦に並べた４個のコインの中心を結ぶ直線と、横に一列6個並べた段の左端のコイン（○で示す。４個あります）の中心を結ぶ直線との距離をwとすると
L'' = 7h+1 
L''=5x+6+w
h^2=1-((1+x)/2)^2 
(h-1/2)^2+w^2=1
となり、その結果（解析的に示すのはしんどいのでお任せして、数値だけ示すと）
w≒0.932699297
x≒0.018377
h≒0.86065
L''≒7.02458
αmin≧11.6190
が得られました。

　かくて、これまで具体的に求めたαminの存在範囲は
12.507＞αmin＞11.619
となりました。1cm近い幅があり、特に上限の方はまだまだ改良の余地があります。

stomachman · Answer

No.11で計算した下限も、まだ改良できます。というのも、最も左側にある黒丸で示したコインはまだ0.Xミリほどガタガタ動ける。これを詰めるように隙間を調節してやることが可能なんですが、もうこうなると簡単な幾何学では計算は困難でしょう。
コンピュータで探すというのも実は容易なことではありません。近似解を与えて微調整させるだけでもなかなか難しいもので、全然違う配置パターンを探すとなると、これはもう凄いことになってしまいます。
ですから、この問題のミソは、(5)の言い換え「一定のサイズのコイン50個を配置できる最小の正方形を求む」に帰着できる、という点にあって、そこから先はおいそれとは手が出ない。専門家が本気で取り組むレベルの問題になっちゃうんです。
stomachmanとしてはここまででギブアップ。

hidearex · Answer

完全に誤解してますね。。。私が！！

失礼致しましたm(__)m

stomachman · Answer

stomachmanです。

No.8で、copy & pasteを失敗したみたいです。
>　L' = 7.947 cm
は間違いで
L' ≒ 7.046cm
と訂正します。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
ちなみに(1)～(5)の言い換えをもう少し厳密に書いてみます。
n={1,2,..,50}、点の列をP[i]（i∈n)、２点P,Qの距離をd(P,Q)、実数の集合をRと書くことにすると、

(1)は
A={α | α∈R∧∀P( ∀i(i∈n→P[i]∈S) → ∃i∃j((i∈n∧j∈n∧i≠j)∧d(P[i],P[j])≦α))}
という集合の下限を求める問題、
(2)は
B={α | α∈R∧∃P( ∀i(i∈n→P[i]∈S) ∧ ∀i∀j((i∈n∧j∈n∧i≠j)→d(P[i],P[j])≧α))}
という集合の上限を求める問題です。

　AとBは１個の要素αminを除いて、互いに実数の補集合になっています（A∪B = R, A∩B={αmin}）。なぜなら、論理式
∀P( ∀i(i∈n→P[i]∈S) → ∃i∃j((i∈n∧j∈n∧i≠j)∧d(P[i],P[j])≦α))
の否定が
∃P( ∀i(i∈n→P[i]∈S) ∧ ∀i∀j((i∈n∧j∈n∧i≠j)→d(P[i],P[j])＞α))
に他ならないからです。そして、
∀α∀β（(α∈A∧β∈B) → α＞β)

　さて、平面上に直交座標系<x,y>を決め、S(L)を、中心が原点にある一辺Lの正方形
S(L)={<x,y>| |2x|≦L ∧ |2y|≦L}
とします。中心がPにある直径αのコイン (α＞0)が占める領域C(P,α)は
C(P,α)={<x,y>|d(<x,y>,P)＜α/2}
です。もしP∈S(α)ならば、コインが占める領域C(P,α)は
S(L+α)={<x,y>| |2x|≦L+α ∧ |2y|≦L+α}
という正方形の中に必ず納まる。つまり
C(P,α)⊂S(L+α)
です。（より正確には、S(L+α)の四隅を半径α/2の円弧で丸めた形の中に必ず納まる。）つまりまた、S(L+α)に納まるコインの中心Pは必ずP∈S(α)である。まとめると
∀α(α＞0→∀P((P∈S(α))⇔C(P,α)⊂S(L+α))
である。
また「２個のコインC(P,α), C(Q,α)が重なりあわない」という命題をF(P,Q,α)と書けば、これは「C(P,α)∩C(Q,α)が空集合」ということと等価であり、すなわちF(P,Q,α)の必要十分条件は
d(P,Q)≧α
です。そして
αmin＞0
も自明です。だから(2)を次のように書き換えることができる。
C={α | α∈R∧α＞0∧∃P( ∀i(i∈n→C(P[i],α)⊂S(70+α)) ∧ ∀i∀j((i∈n∧j∈n∧i≠j)→F(P[i],P[j],α) ))}
の上限を求める問題。これが(3)です。

次に(4)。これは(3)の座標系をx,y共に1/α倍に相似変換したものに過ぎません。αそのものには何の影響もないので、
C={α | α∈R∧α＞0∧∃P( ∀i(i∈n→C(P[i],1)⊂S(70/α+1)) ∧ ∀i∀j((i∈n∧j∈n∧i≠j)→F(P[i],P[j],1) ))}

(4)から(5)への言い換えは自明でしょう。

hidearex · Answer

たびたびスミマセン。。。

＞正方形を7×7=49個の小正方形に分けると、任意の2点間の
＞距離の最大値は10√2となります。 
＞この事例は、10√2＞αだと当てはまりません。 

最大値じゃなくて最小値でした(;^_^A アセアセ

あと、繰り返しになりますが　「αの最小値＝10√2 」ですが
これが「αの最小値＝いちばん距離の近い二点の距離」ということには
なりませんよ！！

stomachman · Answer

ご質問には何もおかしな点はありません。ランダムなんて一言もいってませんしね。

(1)「一辺70cmの正方形の領域Sの中から50個の点P[i] (i=1,2,....,50)をどう選んでも、
∃i∃j(i≠j ∧ P[i]とP[j]の距離がα以下）
となるようなαの下限を求める」という問題。言い換えれば、

(2)「一辺70cmの正方形の領域Sの中から50個の点P[i] (i=1,2,....,50)を旨く選んで、
∀i∀j(i≠j → P[i]とP[j]の距離がα以上）
とできる、そういう選び方が存在するαの上限を求める」という問題。さらに言い換えれば、

(3)「一辺(70+α)cmの正方形の領域Sの中に直径αcmのコイン50個を互いに重なり合わないように並べることができるようなαの上限を求める」という問題。さらに言い換えれば、

(4)「一辺(70/α+1)cmの正方形の領域Sの中に直径1cmのコイン50個を互いに重なり合わないように並べることができるようなαの上限を求める」という問題。さらに言い換えれば、

(5)「直径1cmのコイン50個を互いに重なり合わないように並べることができるような、最小の正方形の一辺の長さをLminとするとき、αmin=70/(Lmin-1)を求めよ。」という問題です。

●この手の問題はたいてい難しい。一般に、上限をご質問に書かれたような方法（10√2＞αminが既に得られていますね）で下げて行き、また実際にコインの並べ方を示すことで下限を上げていって追いつめるんですが、上限=下限に到達するのは容易でない。

●まず下限を検討してみましょう。
　直径1cmのコインを７個一列に並べ、その上に「たわら」を重ねるように６個のコインを一列に並べる。この１３個のセットを４段積み重ねて、都合52個のコインを並べてみますと、幅が7cm、高さは((7√3)/2+1)cmとなり、一辺L=((7√3)/2+1)≒7.062cmの正方形に納まります。
従って、
αmin≧70/(L-1)=(20√3)/3≒11.547cm
という下限が得られます。
　ところで、この並べ方ですと、縦には一杯ですが横に0.062cmの隙間が残っています。だから、はじめに並べる７個のコインの間にちょっとだけ等間隔で隙間を開けてやれば、その上に乗る６個のコインにも同じだけ隙間があくと共に、高さが少し下がる。この方法で52個のコインを納めるもう少し小さい正方形が得られます。隙間をx cmとし、正方形の一辺の長さをL'とします。一列目のコインの中心を結んだ線と、２列目のコインの中心を結んだ線との距離をhとすれば、
L' = 7+6x
L' = 7h+1
h^2=1-((1+x)/2)^2
という連立方程式が得られ、
x=14/(√193)-1≒0.0077cm
L' = 7.947 cm
α' = 70/(L'-1) = (5√193)/6≒11.58 cm
従って、
αmin≧(5√193)/6≒11.58 cm
と下限が改良されました。
　この正方形には、まだコイン２個が余計に入っている。これらを取り除いて丁度50個を入れることにすることで、もうちょっと改良できる。具体的には、まず一辺Lの正方形を用意します。なるべく右に詰めるようにして、「たわら」型に積むんですが、１段目は右に寄せて６個、２段目は５個、３、４、５段目は６個、６段目は５個、７、８段目は６個を積む。これで46個です。あと４個を、左に空いているスペースに、縦一列に揃うように嵌め込む。こうすると、左の隙間がL'の場合より一層大きくなります。だからその分、コインの間隔を大きくでき、従って高さを下げられる。（こうなってくると具体的な計算は面倒ですんでご勘弁。）
　このようにして正方形を小さくする（つまりαminの下限を改良する）ことができる。

●一方、これとは似ていない詰め込み方が存在しないとも限らない。ですからαminの上限を押さえ込んでいく（どうやってもコイン50個が入らない事を示せる正方形を、大きくしていく）ことも重要ですね。
直径1cmのコイン50個の面積は 50π/4 ≒39.26、ですから、一辺がL#=√(50π/4 )≒6.267cmの正方形に納まる筈がないのは自明です。従って、
10√2≒14.14＞13.29≒70/(√(50π/4 )-1)＞αmin
という訳で、上限はあっさり改良されました。まだまだ絞れそうです。

最終決着はなかなか難しいと思います。

hidearex · Answer

確認していただきたいのですが、
＞「１辺70cmの正方形の内部(辺上含む)に、50個の点を“適当”にばらまく。
＞このとき、２点間の距離がαcm“以下”になるような２点が“必ず”存在する。」 
＞上記の主張が成り立つようなαの最小値を求めよ。（回答：α＝10√2 ）

“ ”で強調した部分をもう一度確認してください。


で、あなたがNO.3で補足してますが
＞「（１辺70cmの正方形の内部(辺上含む)に、）50個の点を“どのように”並べたとしても、
＞そのうち“一番距離の近い”二点を選ぶと、その距離はαcm以下となる。」 
＞上記の主張が成り立つαの最小値を求めよ。 
＞α=70√2で主張が成り立つのは明らかです。 
＞α=10√2の時も証明できました。 
＞このようにαの値を小さくしていけば、いつかは主張が成り立たなくなるはずですが、
＞その境界線が知りたいのです。 

その境界線が、α=10√2=『αの最小値』です。

＞「」内の主張が“成り立たない”ようなαの値に対して、以下のことが言える。 
＞「どの二点をとっても、その間の距離がαcmより大きくなるような並べ方が(少なくとも一つ)存在する。」 
＞しかし、ここで、どの二点間の距離も10√2より大きくなるように50個の点を並べるということは不可能だと思います。(紙に書いてやってみました) 

“成り立たない”ようなαの値を元にした定理？ですので当然です。

前後しますが
＞最終的にstargazerさんは　10√2＞α となる値があることを証明したい、ということ
ですよね？

正方形を7×7=49個の小正方形に分けると、任意の2点間の距離の最大値は10√2となります。
この事例は、10√2＞αだと当てはまりません。

よって、10√2=『αの最小値』です。

長々と書きましたがいかがでしょうか？
よけいに混乱させてしまったらスミマセン(;^_^A アセアセ

hidearex · Answer

ちょっと内容を端折りすぎました～(^-^;)

＞しかし、直感的に、これより小さな値でも成り立ちそうなので、この問題を考えました。 

ということから、最終的にstargazerさんは　10√2＞α となる値があることを
証明したい、ということかと思ってＮＧですと回答したのですが。。。

慣れない分野でたまに回答するとこれだ(;^_^A 　失礼しました。

noname#30727 · Answer

＞また、No.2 の人の言っておられることは、何か勘違いされています。

あいや～、starfloraさん、ご指摘ありがとうございます。
間抜けな回答をしてしまいました。

linus3030 · Answer

成り立たない条件を考えてみましょう 
正方形の面積をＳ 
適当な点の数をｎとし 
正方形内の任意の場所をｎの近傍としてグループ分けします。（たとえば一番近い点ｎのグループに属す） 

とするとグループはｎ個でき 
すべての２点の距離がα以上になるならば 
各グループはかならず半径α／2の円をふくみますよね。 
で、各グループの面積の平均は 
Ｓ／ｎになりますが平均値の定理により 
すくなくとも１グループはこれより大きい面積が必要になります。 

ところが各辺がαで鋭角が６０度の菱形を考えると 
この面積は√３／２ｘαｘαですので 
全面積に対するうちの半径α／2の円の占める割合は 
これを上回ることはできません。 
Ｓ／ｎ＞√３／２ｘαｘαを満たさなければ 
αの距離を保てません、（コインのひきつめ問題です。） 

Ｓ／ｎ＝√３／２ｘαｘαを解くと 
αは10√2よりももっと大きくてもよいようです

自作問題(図形？)です

またまたstomachmanです。

No.11で計算した下限も、まだ改良できます。

完全に誤解してますね。

stomachmanです。

たびたびスミマセン。

ご質問には何もおかしな点はありません。

確認していただきたいのですが、

この回答への補足

ちょっと内容を端折りすぎました～(^-^;)

この回答への補足

＞また、No.2 の人の言っておられることは、何か勘違いされています。

成り立たない条件を考えてみましょう

この回答への補足

似たような質問が見つかりました

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング