自作問題(図形？)です

質問

自分で考えた問題なんで、解けるかどうかも分かりません

「１辺70cmの正方形の内部(辺上含む)に、50個の点を適当にばらまく。このとき、２点間の距離がαcm以下になるような２点が必ず存在する。」
上記の主張が成り立つようなαの最小値を求めよ。

これの元ネタは、αでなく10√2 という具体的な値で、これが成り立つことを証明せよというものです。
この場合は、正方形を7×7=49個の小正方形に分けると、鳩の巣原理によって明らか、ということでした。
しかし、直感的に、これより小さな値でも成り立ちそうなので、この問題を考えました。
作ったはいいものの、私には解けそうにありません。
誰か代わりに解いてやってくれませんか？
できれば、高校レベルの知識で分かるように説明してほしいと思います。

回答No.8

stomachman

ご質問には何もおかしな点はありません。ランダムなんて一言もいってませんしね。

(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
という訳で、上限はあっさり改良されました。まだまだ絞れそうです。

最終決着はなかなか難しいと思います。

お礼

丁寧な回答ありがとうございます
忙しい上に、論理式に慣れていないので、まだ全部読めていませんが、大体の流れは分かりました
(1)から(2)の言い換えは自分もすぐに分かったんですが、(3)への言い換えは思いつきませんでした
これは、なかなかトリッキーですね
紙に書いてみてなるほどな～と感心してしまいました

それにしても、この問題はけっこう厄介な問題のようですね
多少予想はしていましたが、一般的な解法というのはないのかもしれません
今まで、きれいに証明できる問題ばかりやってきたので、少し戸惑いがあります