パズルの国のアリス

寂しがり屋の蟻たち(解答)

 まずnがあまり大きくない場合を個別に考えてみよう。形成されるグループはどれも蟻が2匹以上になるからn=2とn=3の場合は全部が1グループになるしかない。

 n=4の場合,全部が1グループになるか,2匹ずつのグループが2つできるかのいずれかだが,それぞれがどのような確率で生じるかが問題だ。フェンス上の蟻を左からa0a1a2a3とする。a0a1に向かって右に進み,a3a2に向かって左に進むことは間違いないので,グループ数を定めるにはa1a2の進む方向がカギになる。diaiー1aiの距離とすると,d1d2ならa1は左向きに進み,反対にd1d2なら右向きに進む。同様に,a2d2d3なら左向き,d2d3なら右向きに進む。表にすると

のようになる。すぐに見て取れるように,d1d2d3の場合だけが2グループになり,ほかは1グループだ。

 ただ,ここで初心者が陥りがちな確率に関する誤解について注意しておこう。それは,上の表の4通りの場合が均等に生じると考え,グループ数の期待値を(1+2+1+1)/4=5/4とするのは誤りだということだ。実際は,真ん中の2通りは一番上や一番下の場合よりも2倍生じやすい。なぜかというと,事象d1d2と事象d2d3が独立ではないからだ。数値diは互いに無関係だと考えてよいから,この2つの事象はどちらも確率1/2で生じるが,それらが同時に生じる確率は,その積1/4ではなく1/6なのだ。

 直感的には次のように考えればよいだろう。d1d2が生起している場合,d3についてはd1d2d3d1d3d2d3d1d2の3通りの可能性があり,それぞれが均等に起こる。この結果,d1d2d3が起こる確率は1/6になり,d1d2d3が起こる確率は2/6=1/3だ。

 他の場合も同様に確率を計算でき,結局n=4の場合,形成されるグループ数の期待値は
1×1/6+2×2/6+1×2/6+1×1/6=4/3となる。

 上に述べたような誤解を避けるには,場合分けの時点でd1d2d3の大小順をすべて考えて,

のように分類するのが賢明だろう。そうするとグループ数の期待値は(1+2+1+1+2+1)/6=4/3となることがわかる(この場合でも,上の6通りが均等に起こることを疑う読者がおられるかもしれないが,各蟻の位置はフェンス上の独立な一様分布に従うから,隣接する2匹の蟻の距離diiと無関係に同一の分布を持つことは納得していただけるだろう)。

 同様にn=5の場合,(実際に書き出すのは省略するが)d1d2d3d4の大小順24通りをすべて調べると,平均で40/24=5/3個のグループができることがわかる。

 ここまでから,n=2の場合は例外だが,一般にグループ数の平均値はn/3になることが予想される。実はこの予想は正しい。

 当然だが,各グループには分類表中でaiー1→←aiとして示される相互に近づいていくペアがちょうど1組含まれ,そのペアを核としてグループが形成される。少し考えればわかるが,ペアaiー1→←aiができるためには,d1d2,・・・・・・,dn−1と並べたときにdiの隣にそれより小さいdi−1di+1がないことが必要十分だ。だから,分類表から自分より小さい要素を隣に持たないdiをすべて数え上げることで,n≧3の場合にそのようなdiの総数がn!/3であることを数学的帰納法によって示すことができる。すると,分類パターンの総数が(n−1)!であることより,ペア数(すなわちグループ数)の期待値はn/3となる。

 さて,隣に自分より小さい要素を持たないdiの総数がn!/3となることの数学的帰納法による証明だが,まずn=3の場合は,直ちにわかるように総数は2だから3!/3=2より正しい。nのときに正しいと仮定して,d1,・・・・・・,dn−1を大小順に分類した(n−1)!個の全パターンの表を作り,diが自分よりも小さいdi−1di+1を隣に持たないときdiに印を付ける。このとき,仮定より全部でn!/3個のdiに印が付く。さて,この分類表をもとにして,要素が1つ増えた場合の分類表を考えよう。d1,・・・・・・,dn−1よりも小さい要素dをこの列のどこかに挿入する場合,dの挿入位置にはn箇所の可能性があり,これがn個のものを大小順に並べた総数(n−1)!×nn!個のパターンを生み出す。1つのパターンがn個に分かれるので,印を無条件にコピーすると,元からある印の総数はn×n!/3になる。dは最小の要素だから,dには当然印が付き,各パターンに新しい印が1つずつ増えるので総数ではn!増える。ところが実は,元の印を無条件にコピーしたのはやりすぎだ。diに印が付いているとして,その両隣のどちらかにdが挿入された場合は,自分よりも小さいものが隣に来たのでdiに付いていた印が消える。こうして元々印の付いていた要素の隣にdが来たときにはその印が消えるので,その分2×n!/3を差し引いて,分類表中の印の総数は

である。

 しかし,nが大きいときには,数学的帰納法を遂行するよりも次のような直感に訴える考え方が簡便かもしれない。アイデアは,1匹の蟻Aに着目し,それが別の蟻BとペアA→←Bを作る確率を計算することだ。

 Aの一番近くにいる仲間をBとしよう。すなわちA→BまたはB←Aである。議論は左右対称だからA→Bと仮定し,このときさらにA→←Bとなる条件付き確率を求めたい。A,Bの位置座標をそれぞれabとし,AとBの距離をdbaとすると,A→Bとなるための条件はほかのどの蟻もAからd以上離れていることだ。すなわち[adad]という長さ2dの区間にはAとB以外の蟻がいない。

 一方,A→←Bとなるための条件はほかのどの蟻もAとBの両方からd以上離れていることだ。言い換えると,[ada+2d]という長さ3dの区間にAとB以外の蟻がいない。やや厳密性を欠く直感的な議論であることは認めざるを得ないが,たくさんの蟻がフェンス上にいるとき,長さ2dの区間に蟻がいないということは,それを含む長さ3dの区間にいないということよりも3/2倍起こりやすいと考えると,先の条件付き確率が2/3になることがわかる。こうして,各蟻が別の蟻とペアを作る確率が2/3だとすると,n匹の蟻の中にはペアを作っている蟻が平均で2n/3匹いる。各ペアは2匹の蟻で構成されるから,ペア数(すなわちグループ数)の平均はn/3ということになる。

 上の議論はいささか乱暴だが,問題の次元を拡張するような場合に非常に有効だ。n匹の蟻がいて,各蟻の位置が定円盤上の独立な一様分布に従うとき,同じように動いてグループを作るとしよう。蟻AとBの距離をdとするとき,A→BとなるのはAを中心とする半径dの円(下図の左の円)内にAとB以外の蟻がいないことであり,A→←Bとなるのは,A,Bを中心とする半径dの2つの円(下図の2つの円)内のどちらにもほかの蟻がいないことだ。したがってA→BのもとでA→←Bとなる条件付き確率は,だいたい面積比

となり,グループ数の平均値はpn/2=0.31075nくらいになる。

問題はこちらです