2013-04-18

答えが求めやすい場合、２種

昨日のMIKU
Hさんが話題提供
- 10メートル四方の正方形領域に101個のボールを置くとき、全ボールペアの最短距離は $\sqrt{2}$ メートル以下(より短い)ことは鳩ノ巣原理を使うと示せる。細胞の配置とかに応用できそう、と
鳩ノ巣原理:『n 個の物を m 個の箱に入れるとき、n > m であれば、少なくとも1個の箱には1個より多い物が中にある、という原理』(Wikipedia)
100個のボールは、１０メートル四方の正方形を１０ｘ１０＝１００等分割したセルに入れることができる。１０１番目のボールは１００個のセルのどこかに入れるしかない(鳩ノ巣原理)。少なくとも１つのセルには２個のボールが入った。セルは１ｘ１の正方形で、この正方形の中に２点をとるとき、その最長距離は $\sqrt{2}$ メートル(この正方形は直径 $\sqrt{2}$ メートルの円に内接しており、…）
話を一歩進めよう、ということになった。１０１個を１００個と１個に分けたのは $n^2+1;n=10$ という分け方なので、 $n=1,2,...$ と考えればよい。こうすると１ $L$ の正方形に $k=n^2+1$ 個を置くとき、 $\frac{1}{n}\sqrt{2}L=\frac{1}{\sqrt{k-1}}\sqrt{2}L$
話をさらに進めよう、ということになった。 $k=n^2+r;r=0,1,2,...,(n-1)$ ですべて網羅されるけれど、 $r=1$ の場合はわかったから、 $r=2$ や $r=n-1$ の場合ってどうにかならないの？と
良い案ないままに、「具体的にどういう配置にするとよい」のかが話題になった
$r=1$ の場合も、結構うまく配置できないようだ
ここで同じサイズの円の「最密充填」(円充填)をしてその中心をボールの位置とみなすっていうのは、この問題の条件に合っている(近い)ようだということになり、それで考えてみることになった
初期例は $k=7$ 。これは、１個の円の周囲に６個の円が接しているとき。
ここから、正６角形に外接する正方形のうち最小のものは？という問題に切り替わった
正六角形と正方形の対称性から、考えるべき配置は２通りある(正方形の１辺と正六角形の１辺とが平行な場合と、そのように平行な場合を変化させて次にまた平行になる場合とのちょうど中間の状態の場合の２通り)ことがわかった。そのどちらの場合に正方形が小さいかの確認をした(平行ではない場合)。このとき正方形の１辺の長さは、正六角形の１辺(２ボール間距離)の $X=\frac{\sqrt{3}+1}{\sqrt{2}}$ 倍であることが示せた
２つの配置状態のうち、小さい正方形はわかったので、それ以外の状態がより小さくないことの説明がつくことを確かめた
次に、 $k=7$ 以外に最密充填できる場合は？となり、それは、hexagonal latticeと呼ばれる、数列id:A003215、1, 7, 19, 37, 61, 91, 127,...が該当することがわかる。この数列は $S(m+1)=S(m) + 6m$ なる関係にあり $S(m)=3m^2-3m+1$ ( $m=2$ のときに７個)。
すると１辺 $L$ の正方形に $S(m)$ 個のボールを入れたときのペアワイズのボールの最短距離の上限は $\frac{m-1}{X}L$ だということになる。
今 $k=S(m)$ のとき $Y(k=S(m)) = \frac{1}{(m-1)X}L$ という式と $k=n^2+1$ のとき $\frac{1}{n}\sqrt{2}L$ という関係だということがわかった。
それぞれ、 $m,n$ が自然数である場合だけれど、ま、それ以外もそうだと近似してしまえ、と。

k <- 1:500
n <- sqrt(k-1)
m <- (1+sqrt(1-4*(1/3-k/3)))/2
X <- (sqrt(3)+1)/sqrt(2)
A <- sqrt(2)/n
B <- 1/(X*(m-1))

plot(k,A)
plot(k,B)
plot(A,B)

abline(0,1,col=2)