人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

「ビーチで、前から30人の女性が順番に歩いてくる。このうち一番の女性に声を掛けたい。どんな戦略でいくのがいいか?」
という問題の解法を教えてください。
確か、「はじめの数人はやりすごして、次に今までで一番の女性が現れてきたらそれに決める」というような答えだったと思ったのですが…。
聞くところによると、高校の受験数学の確率で出てくる問題だとか。
この証明というか、答えの詳しい説明というか、そういうことについて扱っているページがあればお教え頂ければ幸いです。

●質問者: maiko8
●カテゴリ:学習・教育 科学・統計資料
✍キーワード:受験 女性 戦略 数学 確率
○ 状態 :終了
└ 回答数 : 6/6件

▽最新の回答へ

1 ● KDDI
●10ポイント

http://www.system-azure.co.jp/dance/azure0008.html

蒼天舞曲 #0008:決断

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

この中に

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

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

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

・二股はかけられない。

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


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


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

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

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

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

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

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

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

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

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


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

◎質問者からの返答

な、な、な、なるほど。

たぶんこれです。これと同じです。

そうかぁ…。「1番を求める」のは、半分までなんですね。それ以降は、2番でも決めないと、と。なるほど。勉強になります。

ちなみにこれの解答というか証明というか、もっと詳しい話はありませんでしょうか。

関連して他にもありましたらお教え頂ければ幸いです。


2 ● Baku7770
●5ポイント

http://www.njima.elec.keio.ac.jp/joho2004/joho2004-2.pdf

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


これはOR(オペレーションズ・リサーチ:作戦研究)と呼ばれる情報工学の一分野として昭和50?60年頃まで流行った分野です。ORで簡単で一番有名なのはLP(リニア・プログラミング:線形計画法)というのがあります。


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


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

◎質問者からの返答

うーん…。

秋山仁先生の正解もこんな話だったのかなぁ…。

よくむずかしい理論を簡単に証明できることが

すごい、と受験の時にやったのですが。


3 ● grim
●15ポイント

http://home2.highway.ne.jp/koji/cool/seikou.htm

???????A????????????u?T?????[?}????l?i?v

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

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

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

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


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

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

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


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


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

◎質問者からの返答

なるほど…。簡単には証明できない、のでしょうか。ちょっとがっくり。

でも参考になりました。本当にありがとうございました。

ほかにも何かありましたら幸いです。


4 ● grim
●50ポイント

http://www.hatena.ne.jp/1113472734#

人力検索はてな - 「ビーチで、前から30人の女性が順番に歩いてくる。このうち一番の女性に声を掛けたい。どんな戦略でいくのがいいか?」 という問題の解法を教えてください。 確か、「はじ..

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

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

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

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

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

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

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

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

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


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

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

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

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

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


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

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


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

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

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

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

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

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

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


ちなみに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番目以下に価値を見出さないので、最後のぎりぎりまで見極める人が幸せになれるらしい。


間違ってたらゴメン。

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

以上です。

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

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

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

◎質問者からの返答

うむむ。ありがとうございます。

なるほど。なるほど…。最適でも8%…。

うむ。面白いです。ありがとうございました。お疲れ様でした。


5 ● fromboston
●10ポイント

http://people.bu.edu/koba/personal/0502.htm

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


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


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

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


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


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

◎質問者からの返答

うむむ。なるほど。色々な考え方が。ありがとうございました。


1-5件表示/6件
4.前の5件|次5件6.
関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ