区間が重なる確率の問題－ある区間が他のすべての区間と重なっている確率は?　|ニッセイ基礎研究所

◇ 技巧的な説明を試みる

そこで、かなり技巧的な説明を試みることとなる。“Mathematical Puzzles”(Peter Winkler, CRC Press, 2021)には、このパズルの解答が付されている。その概要は、次のようになる。

あるランダムに選んだn個の区間の状態に対して、うまく(n-2)個を除去して、最後に2個の区間だけが残る状況を作り出す。(n-2)個の区間の除去は、次のように行う。

1～2nの各点に対し、1～nまでのn個の点を「左サイド」、(n+1)～2nまでのn個の点を「右サイド」と呼ぶことにする。そして、(2n-4)個の点に、A(1), B(1), A(2), B(2), …, A(n−2), B(n−2)をラベル付けする。

まず、nにA(1)をラベル付けする。そして、B(1)をA(1)がなす区間の相手の点にラベル付けする。次に、A(j)とB(j) (1≦j≦n-3)をラベル付けしたときに、A(j+1)とB(j+1)を次のルールでラベル付けする。

・B(j)が左サイドにある場合は、A(j+1)は、まだラベルが付けられていない右サイドの左端の点にラベル付けする。B(j+1)をA(j+1) がなす区間の相手の点にラベル付けする。

・B(j)が右サイドにある場合は、A(j+1)は、まだラベルが付けられていない左サイドの右端の点にラベル付けする。B(j+1)をA(j+1) がなす区間の相手の点にラベル付けする。

ラベル付けされた点がなす区間を除去して、最後に残った2個の区間を構成している4つの点に注目する。4つの点は、(1)左サイドに2つ、右サイドに2つというケースと、(2)左サイドに1つ、右サイドに3つというケースのどちらかになる。

各点へのラベル付けのルールから、これらの4つの点の間に、除去した区間の片方の点、A(1), …, A(n−2)があることになる。4つの点から2つの区間を作る状態として、ランダムに選んだ元の状態を含めて、3つの状態があり得る。この3つの状態のうち、(1)で左サイドと右サイドの点から区間を作るか、または(2)で左サイドの点と右サイドのより右側の2つの点のどちらかから区間を作る、2つの状態は「ある区間が他のすべての区間と重なっている」状態となる。残り1つは、(1)で左サイドの2点がなす区間と右サイドの2点がなす区間、(2)で左サイドの点と右サイドの左側の点がなす区間と右サイドの真ん中と右側の点がなす区間が重ならないため、そうならない状態となる。3つの状態は等しい確率で起こるため、ある区間が他のすべての区間と重なっている確率は2/3となる。

以上が説明の概要だが、細かい点の厳密さを欠いている。詳細を確認したい方は、前述の文献の解答をご覧いただきたい。

ごちゃごちゃと文章で示されても、よくわからないかもしれない。そこで、冒頭に図示したn=5の場合の5個の区間の状態を例に、この内容を図で見てみよう。

まず、冒頭に示したn=5の例を再掲する。

ランダムに選んだ元の状態 ([2,10]と[6,8]の組み合わせ)

これに対して、ラベル付けのルールに基づくと、青色の区間[2,10]と、紫色の区間[6,8]の2つの区間を残して、残り3つの区間を除去することになる。これらの2区間を構成している2, 6, 8, 10の点の組み合わせを変えると、次の2つの状態ができる。(赤色と水色と緑色の区間はそのまま記す。)

[2,6]と[8,10]の組み合わせ

[2,8]と[6,10]の組み合わせ

これらの3つの状態のうち、[2,10]と[6,8]の組み合わせと、[2,8]と[6,10]の組み合わせは、ある区間(青色の区間)が他のすべての区間と重なっている状態となっている。

一方、[2,6]と[8,10]の組み合わせは、どの区間も他の全ての区間と重なってはおらず、ある区間が他のすべての区間と重なっている状態とはなっていない。

つまり、問題の確率は2/3となる。

このように、一応説明は付いたものの、まだ納得感がない、腑に落ちないという方もいるのではないだろうか。

◇ 数直線の端と端をつないで円にする

そこで、なんとか少しでも納得感を得たいという方に向けて、“The Art of Mathematics: Coffee Time in Memphis”B. Bollobás(Cambridge U Press, 2006)に示されている解答も見ておきたい。その概要は、次のようになる。

まず、数直線の0の点と(2n+1)の点を結んで、円にしてしまう。この結んだ点をXとする。n個の区間で、同じ区間の端点に同じラベルを付けていく。円をXから時計回りに進み、どれか同じラベル(aとする)の2つ目の点に行き当たった段階で、進む方向を反時計回りに変える。そして、どれか同じラベル(bとする)の2つ目の点に行き当たった段階で立ち止まる。

Xとaとbの位置関係について考えてみる。まず、aはXの右側にある。反時計回りに進んだときの1つ目のbは、2つのaの間にあるか、Xとaの間にあるか、Xより左側にあるかの3通りであり、2つ目のbはXより左側にある。このため、X、2つのa、2つのbの順番を左から書くと、(1)bXaba、(2)bXbaa、(3)bbXaa、の3つが考えられる。

(1)や(2)の場合、もしbを付した2点からなる区間bbとは重ならない区間(その区間をなす2つの点にcのラベルを付してccと表す)があったとすると、Xとbとcの位置関係は、bXccbまたはbccXbとなるが、bXccbではcがaの代わり、bccXbではcがbの代わりとなるため、aとbのラベル付けの方法からこうした状況にはなり得ない。つまりこうした区間ccはない。

一方、(3)の場合、区間aaにも区間bbにも重なっている区間ccがあるとすると、cがbの代わりとなるはずであり、aとbのラベル付けの方法からこうした状況にはなり得ない。つまりこうした区間ccはない。

(1)、(2)、(3)の3つの順番は、同じ確率で生じうる。このうち、(1)と(2)の2つの順番のときにだけ「ある区間が他のすべての区間と重なっている」状態となるため、問題の確率は2/3となる。

こちらの解答も詳細を確認したい方は、前述の文献をご覧いただきたい。この解答は、腑に落ちただろうか。筆者にはあまり自信がないが...。

解答の詳細はともかく、今回の問題では、nがどれほど大きくなろうとも、ある区間が他のすべての区間と重なっている状態になる確率は、2/3となる。2/3という水準が1/2を超えていてかなり大きいことと、それがnによらないことの2点に対して、その意外感を十分に味わっていただければ幸いである。

(参考文献)

“Mathematical Puzzles”(Peter Winkler, CRC Press, 2021)

“The Art of Mathematics: Coffee Time in Memphis”(B. Bollobás, Cambridge U Press, 2006)

「確率パズルの迷宮」(岩沢宏和, 日本評論社, 2014)

日付	タイトル	執筆者	媒体
2025/05/27	気候指数 2024年データへの更新－日本の気候の極端さは1971年以降の最高水準を大幅に更新	篠原拓也	基礎研レポート
2025/05/20	「次元の呪い」への対処－モデルの精度を上げるにはどうしたらよいか?	篠原拓也	研究員の眼
2025/05/13	チェス盤を用いた伝心－愛情と計算力があれば心は通じる?	篠原拓也	研究員の眼
2025/05/09	国民負担率 24年度45.8％の見込み－高齢化を背景に、欧州諸国との差は徐々に縮小	篠原拓也	基礎研マンスリー

区間が重なる確率の問題－ある区間が他のすべての区間と重なっている確率は? | ニッセイ基礎研究所