当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。
（平成２６年２月１５日付け）
さて、これから出会う未知の４人（自分との相性が４人間で序列がつくものとする。）の中で
最も相性が良い人と出会うためには、如何なる戦略をとれば、最も確率よく出会えるかを調
べる。
作戦１：最初の人を選ぶ。
作戦２：最初の人は見過ごし、この人より相性の良い人と出会うと決定する。
作戦３：出会いから２人目まで見過ごし、その後出会った人より相性の良い人に決定。
作戦４：最後まで待ってその人を選ぶ。
もちろん作戦２，３はそれまで出会わないなら最後の人を選ぶことになる。
この作戦１〜４での最高に相性の良い人とカップルになれる確率をそれぞれ求めて下さい。
同様に、１００人の人とお見合いをしたとき、自分と最も相性が良い人を射止めるための確
率を最も高めるときの作戦を立てて下さい。
（答） 作戦１： １/４ 、作戦２： ５/１２ 、作戦３： ３/８ 、作戦４： １/４
作戦：「出会いから３６人目まで見過ごし、その後出会った人より相性の良い人に決定」
（コメント） 以前、どこかで同じような問題を拝見しました。確か、秋山 仁 先生が紹介され
ていたような．．．おぼろげな記憶。
何かを選んだり決めるとき、確率論的には次のように対処するのがベストだそうです。
（１） 最初の２つは良いと思っても、スルーする。
（２） ３つ目を見て、良ければ決める。
（３） ３つ目を見て、悪ければ、４つ目を見る。
（４） 以下、（２）（３）のように、良ければ決めて、悪ければスルーして、次を見る。
このことから、作戦３が一番確率が高いかも．．．。
ただ、人数が少ない４人だと次のように計算してみて、作戦２の方が有利と分かりました。
ｎ人の中から最良の１人を選ぶとき、ｋ人まではスルーして、ｋ＋１人目以降で最良の１人
を選ぶ確率をＰ（ｋ，ｎ）とおく。
（例） ｎ＝２ のとき、 Ｐ（０，２）＝Ｐ（１，２）＝１/２
ｎ＝３ のとき、 123 、132 、213 、231 、312 、321 の６通りが起こりえるので、
Ｐ（０，３）＝２/６＝１/３ Ｐ（１，３）＝３/６＝１/２ （← 213 、231 、312 ）
Ｐ（２，３）＝２/６＝１/３
ｎ＝４ のとき、 1234、1243、1324、1342、1423、1432、2134、2143、2314、2341、2413、
2431、3124、3142、3214、3241、3412、3421、4123、4132、4213、4231、
4312、4321
の２４通りが起こりえるので、
Ｐ（０，４）＝６/２４＝１/４
Ｐ（１，４）＝１１/２４
（↑ 2134、2143、2314、2341、2413、2431、3124、3142、3412、4123、4132）
Ｐ（２，４）＝１０/２４＝５/１２
（↑ 2314、2341、2413、2431、3214、3241、3412、4213、4231、4312）
Ｐ（３，４）＝６/２４＝１/４
（↑ 2341、2431、3241、3421、4231、4321）
上記の計算を一般化してみよう。
確率 Ｐ（ｋ，ｎ）＝最良の人Ａ（ｒ＋１番目）を見いだすために、ｋ人まではスルーして、ｋ＋１人
目以降から最良の人を見いだす確率
つまり、ｋ＋１人目以降のものから、今までに出あった中で最高の人を超える人Ａを見つけ
る確率を最大にする。
まず、明らかに、スルーしていいのは、ｒ人目までなので、 ｒ≧ｋ が成り立つ。
次に、最良の人Ａが、ｒ＋１番目に現れる確率は、１/ｎ で、そのＡに出会う確率は、ｋ/ｒ な
ので、
Ｐ（ｋ，ｎ）＝（１/ｎ）（ｋ/ｒ） ただし、 ｒ＝ｋ、ｋ＋１、・・・、ｎ−１
したがって、上記の手順で、最良の人Ａを見いだす確率は、
Ｐ＝Σr=k〜n-1 Ｐ（ｋ，ｎ）＝（ｋ/ｎ）Σr=k〜n-1 １/ｒ
ところで、ｘ≒０ に対して、ｌｏｇ （１＋ｘ） ＝ｘ−ｘ2/２＋ｘ3/３＋・・・ より、ｌｏｇ （１＋ｘ） ≒ ｘ
なので、 ｌｏｇ ｎ ＝ｌｏｇ ｎ/（ｎ−１）・（ｎ−１）/（ｎ−２）・・・（２/１）
＝ｌｏｇ（１＋１/（ｎ−１））＋ｌｏｇ（１＋１/（ｎ−２））＋・・・＋ｌｏｇ（１＋１/１）
≒１/（ｎ−１）＋１/（ｎ−２）＋・・・＋１/１
＝１/（ｎ−１）＋・・・＋１/ｋ＋１/（ｋ−１）＋・・・＋１/１
＝１/（ｎ−１）＋・・・＋１/ｋ＋ｌｏｇ ｋ
より、 Ｐ＝（ｋ/ｎ）ｌｏｇ（ｎ/ｋ） となる。
このとき、 Ｐ’＝０ とすると、 ｌｏｇ（ｎ/ｋ）＝１ から、 ｋ＝ｎ/ｅ となる。
ｋ＝ｎ/ｅ のとき、Ｐは極大かつ最大となる。
つまり、最初の ｎ/ｅ 人をスルーして、ｎ/ｅ＋１人目以降で最良の人Ａを選ぶ確率が最大と
なる。その確率は、
（ｋ/ｎ）ｌｏｇ（ｎ/ｋ）＝（１/ｅ）ｌｏｇ ｅ
＝１/ｅ ＝１/２．７１８２８１８２８４・・・＝０．３６７８７９４４１１７９５３３・・・
よって、確率は、だいたい３７％ということが分かります。
ｎ人から１人を選ぶ確率は、１/ｎ で、これは、ｎ が十分大きくなると限りなく０に近づくこと
を考えれば、上記手順で最良の人を選ぶ確率が３７％というのは、十分高い確率ですね。
３×０．３７＝１．１１ 、４×０．３７＝１．４８ 、５×０．３７＝１．８５ なので、
ｎ＝３、４、５ のときは、１人をスルーしてから選ぶと最良の人を見つける確率が高い。
６×０．３７＝２．２２ なので、ｎ＝６のときは、２人をスルーしてから選ぶと最良の人を見つ
ける確率が高い。
したがって、ｎ＝１００ のとき、 ｎ/ｅ ＝ １００×０．３６７８・・・＝３６、７８・・・ から、求める
作戦は、
出会いから３６人目まで見過ごし、その後出会った人より相性の良い人に決定
とすればよいことになる。
（コメント） 最初はいくつかスルーして経験を積んだ後に選んだ方が、最良のものを選ぶ確
率が高いということは、人生の選択においても使えそうですね！