「ビーチで、前から30人の女性が順番に歩いてくる。このうち一番の女性に声を掛けたい。どんな戦略でいくのがいいか？」

秋山仁先生の書く「皆殺しの数学」と言う物があります。

この中に

・全部で20人の相手とお見合いをする。

・断った相手とは2度と会えない。

・会う順番はランダムに与えられる。

・二股はかけられない。

この条件で、その20人の中で、事後的に順位を付けることができた場合の順位が3番目以上の相手と結婚するための戦略を考えよ、と言う問題があります。

この場合は以下のようになります。

最初の5人は無条件で見過ごす。

10人目までは、それまでで1番だと思ったら結婚する。

13人目までは、それまでで2番め以上だと思ったら結婚する。

15人目までは、それまでで3番め以上だと思ったら結婚する。

16人目の相手が、それまでで4番め以上だと思ったら結婚する。

17人目の相手が、それまでで5番め以上だと思ったら結婚する。

18人目の相手が、それまでで7番め以上だと思ったら結婚する。

19人目の相手が、それまでで10番め以上だと思ったら結婚する。

20人目の相手とは、ルール上どんな相手でも結婚する。

これを応用して求められます。

　元々は無限に続くビーチで無限の女性がいて報酬（気分が優れているとか落ち込むくらいでしょうか）をどうやって計算するという問題の一部を切り出したものです。

　これはＯＲ（オペレーションズ・リサーチ：作戦研究）と呼ばれる情報工学の一分野として昭和５０～６０年頃まで流行った分野です。ＯＲで簡単で一番有名なのはＬＰ（リニア・プログラミング：線形計画法）というのがあります。

　本当に知りたければ、マルコフ過程もしくはマルコフ連鎖、ｚ変換、ダイナミックプログラミングをキーワードに大きな書店の情報工学関係のコーナーをタイトルで本を探して下さい。お勧めは培風舘書店の「ダイナミックプログラミングとマルコフ過程」ですが古いので多分絶版だと思います。

　実際の問題は状態遷移確率Ｐijの確率行列と報酬行列Ｒijを反復計算して求めます。

私も秋山仁先生の「皆殺しの数学」という本を持っているのですが、

その内容と、そっくりそのまま一緒のことが書いてあります。

女性が回転寿司のネタに変わっただけです。

ただ、本と違って、若干、後半なんかイイ話になっていますが・・・。

具体的な証明については、本にもページにも書かれていませんでした。

「ダイナミックプログラミングの期待値をつかって考えるのだが、数式がやたらと長くなるので、」

との事で省略されていました。

最後に、「１０００人、一万人の人がこの戦略にしたがって結婚を決断すればその人たちの選んだ相手の平均順位が３位になるということである。」という事が付け加えられていて、あなた個人の選んだ人が確実に３位以内になるとは、保証できない、みたいなことが書いてありました。

既にkddiさんが答えている内容なので、あまり役に立てないかもしれませんが。

再びすみません。URLはダミーです。

高校の受験数学の範囲に出てくるとしたらあまり高度すぎるようなものじゃないという事なんですね。ダイナミックプログラミングなんて知らない・・・。

で、数学の得意そうな人、知り合いの中学・高校の数学の先生にメールで聞いてみて、今のところ帰ってきた返事にそれらしきものがこれです。メールをそのまま貼り付けます。

----------------

その問題、許される前提条件が分からなさ過ぎる。

答えの中に「2番目」って単語があるってことは、

1番目を当てるだけの単純確率問題ではなくて

「好み」を度数で表す度数分布を考慮した問題だって事だよな？

それにしては重大な前提条件が２つ抜けているぞう。

１つめは、女の好みと分布の関連性。

アブノーマルな好みの人だと絶対に正規分布にはならない。

（極度のデブ好きなら100人中99人が0点で1人だけ100点とか、

年齢限定で100点になっちゃう人は等確率分布、または人口分布に依存するとか）

それに、本当にごく一般的な好みの人なら正規分布とみなせるのか？

２つめは、これはナンパの価値観といってもいいが、何番目の女を捕まえたら

そいつがどれだけ幸福になるか、という重要な指標「評価関数」が定量化されていない。

「美人以外は氏ね！」という価値観と「平均以上ならOK」という価値観では、

まるでその戦略は変わってきてしまう。要は得点ルールが決まってないって事だな。

答えでは後半で妥協しているが、最後まで1位の美人ちゃんが飛び出す可能性はゼロではない。

「あと2人だ、次がイマイチでも最後待たずに声かけちゃえ！」って判断は、

美人以外に興味の無い人には完璧に「間違った」戦略だよな？

まあ、ここは百歩譲って度数＝価値、と見なしてもいいんだが、

そうすると１つめの分布の定義が出来てないと絶対に評価なんて出来ないぞ、、、。

ちなみに2位以下は無価値として計算すると、

・1人も見送らずに最初に声をかける＝勝率3.33%

・1人見送り、次以降の1番に声をかける＝勝率4.49%

・2人見送り、次以降の1番に声をかける＝勝率4.95%

・3人見送り、次以降の1番に声をかける＝勝率5.37%

　・

　・

・m人見送って(m+1)人目がそれまでで1番の確率がm・(m-1)!／(m+1)!、

それが全体の中で1番の確率は1/(31-m)、

　・

　・

ということで、見送った人数をmとすると、これは以下の式で表せる。

30

Σ｛m×(n-2)!／(n!×(31-n))｝

n=m+1

ちなみに、最適点は「18人見送る」＝勝率8.307%

すなわち2番目以下に価値を見出さないので、最後のぎりぎりまで見極める人が幸せになれるらしい。

間違ってたらゴメン。

----------------------

以上です。

なんか上のほうでいろんな場合をゴチャゴチャ言ってますが、そういうことを考慮しないものとするということだとおもうので、

「一番の女性」＝「二位以降無価値」という条件で出した式でよいのかしら、と思いました。

間違ってたらゴメン、と言われて、まったく私には間違ってるかどうかもわからないので、このまま託します。よろしくお願いします。

URLの2月14日と15日の日記に回答が書かれています．

はじめの n 人をやり過ごすことによって，(1)どんな女性がいるかという情報の正確さが増します（標本調査により母集団の確率分布に対する推測が正確になる）．その一方で，(2)一番良い女性をやり過ごしてしまう危険性が高まります．やり過ごす人数 n は，これら二つの効果がちょうど釣り合うところで決まります．

(2)の効果についての計算は簡単で，はじめの n 人をやり過ごした後で残りの 30-n 人の中に一番の人が残っている確率は (30-n)/30 です．

これに残り 30-n 人の中から一番の人を正確に選ぶことができる確率（f(n)としましょう）を掛けたものを最大化するように n を選ぶと良いわけです．

さて，f(n)とはどのような関数かということですが，一番の女性を選ぶことができる確率は，はじめにやり過ごした n 人の標本から得られる情報量に比例します．標本から得られる情報量は標本数 n が増えると増加しますが，追加１単位あたりの情報量は減少します（つまり，はじめの１人目を観察したときに得られる情報量よりも，１０人を観察した後で１１人目を観察したときに得られる追加的情報量は少ない）．このことは，f(n)が n について増加関数であり，かつ凹関数であることを表します（一階微分が正で，二階微分が負ということです）．若干高校数学の範囲を超えますがチェビシェフの不等式というのがありまして，f(n) は ルートn に比例することが知られています．「大数の弱法則」「ルートn一致性」などをキーワードに確率論や統計論の参考書を参照されれば，詳しい議論が書かれていると思います．掲示板に数式を書き込むのはつらいので，ここは勘弁してください．このへんの議論は高校数学の範囲を超えるかもしれませんが，f(n) が増加関数かつ凹関数であることについては，直感的だと思います．

さて，あとは ((30-n)/30)*sqrt(n) を最大化するだけです．n で微分して =0 とおけばよいです．答えは n=10．つまりはじめの10人をやり過ごして情報を集め，残りの20人から選べということになります．

すいません．自分の回答に補足させてください．大数の弱法則もチェビシェフの不等式も高校数学の範囲みたいですね．高校時代，勉強しなかったもので，すっかり忘れていました．上記PDFファイルの535-537ページに大数の弱法則の説明が書かれています．また標準偏差（情報の不正確さの尺度）がルートnに比例して減少することも説明されています．