次のようなゲームを考えます。
(1)10枚のカードに数値が書かれてあり、見えないようにして置かれています。
(2)書かれている数値は全て異なっていますが、連続しているわけでもなく、最大値も知らされていません。
(3)カードを1枚づつめくっていき、最大値であろうと思われるところで1枚キープできます。キープ宣言はめくった直後のカードについてのみできます。
(4)めくったカードの数値はもちろん記憶しておいてかまいません。(記録しておいてもOK)
(5)全てのカードをさらして、キープしていたカードが最大値なら勝利です。最大値でなければ負けです。
問題:勝利する確率を最大にする戦略を考えなさい。 結構難問です。答えがあるのかどうかも不明です。
とりあえず思いついた戦略:5枚とりあえずめくってみる。その中の最大値を記憶。6枚目から順にめくって記憶した最大値より大きかったらキープして終了。
こうすると、
a)前半5枚に最大値が入っていれば、負け 1/2
b)前半5枚に2番目に大きなカードが入っていて、後半5枚に最大値が入っていれば、勝ち 1/2 x 1/2
c)前半5枚に3番目に大きなカードが入っており、後半5枚に最大値が2番目より先に入っていれば、勝ち
・・・うーむ難しい。
そもそもこんな考え方でよいのか? 何枚か捨ててその情報を頼りに後半勝負するしかないような? 5枚がよいのかどうか?
もともとの問題は、カードn枚でキープできるカードはk枚となっていますが、難しすぎるので10枚、1枚で限定しました。
No.3ベストアンサー
- 回答日時:
キープが複数のときの戦略は、ご友人のほうがはるかにいいですね。
n=100,k=3の場合のその戦略の確率を計算してみました。
最大のカードがi番目にあるときに、それをキープする確率をQ(i)とすれば、求める確率は、
(1/n)Σ[i=1・・・n]Q(i)
Q(i)は、
i≦m1 のとき、Q(i)=0
m1<i≦m2 のとき、Q(i)=m1/(i-1)
m2<i≦m3 のとき、Q(i)=m2/(i-1)
m3<i のときは、
Q(i)=(1-m1/m2)(1-m2/m3)(m3/(i-1))
+{(1-m1/m2)(m2/m3)+(m1/m2)(1-m2/m3)}{1-(i-m3-1)(i-m3-2)/((i-1)(i-2))}
+(m1/m3){1-(i-m3-1)(i-m3-2)(i-m3-3)/((i-1)(i-2)(i-3))}
m1=14, m2=32, m3=64 のときは、0.6725479
m1=13, m2=28, m3=45 のときに、最大0.7012128になるようです。
確率式まで求めていただいて恐縮です。
戦略は考えようでいくらでもありそうで最適なのを見つけるのは相当難しいですね。
最適であるとの証明もできそうもないし。
No.2
- 回答日時:
>nをどんどん大きくしたらどうなるかは不明です。
予想ですが、nを十分大きくすれば、
1/k+1/(k+1)+1/(k+2)+・・・・+1/(n-1)≒∫[k→n](1/x)dx=log(n/k)=1
より、
k/n=1/e≒0.36787944 に収束するのでしょう。
カードn枚でキープできるカードがk枚の場合を考えてみました。
戦略は、
はじめのm枚は見逃す。
m+1枚目からは、はじめのm枚のカードより大きかったらキープする。
1枚でもキープしたあとは、直前にキープした数より大きかったらさらにキープする。
これを、キープがk枚になるまで繰り返す。
この戦略で勝つ確率は、
最大値のカードがはじめのm枚に入っていたら、0
最大値のカードがm+1~m+k枚目に入っていたら、必ず選ばれるので、k/n
最大値のカードがi枚目(m+k+1≦i≦n)の場合は、詳しい説明は省きますが、
1/n × (1-C(i-m-1,k)/P(i-1,k))
となります。
よって、勝利する確率は、
k/n+(1/n)Σ[i=m+k+1・・・n]((1-C(i-m-1,k)/P(i-1,k))
=1-m/n-(1/n)Σ[i=m+k+1・・・n]C(i-m-1,k)/P(i-1,k)
ただし、P,Cは順列、組み合わせの数です。
P(n,k)=nPk
C(n,k)=nCk
度々の回答ありがとうございます。こんなところにもeがでてきますか。数学って面白いですね。
提案された戦略でシミュレーションしてみます。友人が考えている戦略は似ていますがちょい違ってます。
k=3で説明すると。m1<m2<m3の3カ所を決めておきます。
(1)1番目からm1目までは捨てます。
(2)m1+1以降、m1までの最高値を超えたらキープします。それがk1番目だとして、
(3)k1<m2ならm2までは無条件に捨てます。k2>=m2なら(4)の処理。
(4)それ以降は、それまでの最高値を超えたらキープします。それがk2番目だとして、
(5)k2<m3ならm3までは無条件に捨てます。k2>=m3なら(6)の処理。
(6)それ以降は、それまでの最高値を超えたらキープします。
ようはキープしたカードの位置によって無条件に捨てる区間を設ける訳です。
n=100,k=3のときm1=14,m2=32,m3=64で確率約0.7
No.1
- 回答日時:
古くからある「見合いの問題」や「海辺の美女問題」に似ていますが、最大値かどうかだけならこのゲームのほうが簡単でしょう。
キープできるカードが複数の場合は難しいでしょうが。
戦略としては、何枚か捨ててそのあとにそれより大きい数を選ぶという方法しかないように思います。
で、5枚捨てる場合の確率ですが、
もし最大値のカードが前半5枚に入っていたら勝つ確率は、0
最大値のカードが6枚目だったら、必ずそれが選ばれるので勝つ確率は、1/10
最大値のカードが7枚目だったら、はじめの6枚の中の最大値が前半5枚に入っていたら、7枚目が選ばれるので勝つ確率は、1/10×5/6
同様に、最大値のカードが8枚目だったら、それが選ばれるので勝つ確率は、1/10×5/7
最大値のカードが9枚目だったら、それが選ばれるので勝つ確率は、1/10×5/8
最大値のカードが10枚目だったら、それが選ばれるので勝つ確率は、1/10×5/9
よって、最大値のカードが選ばれる確率は、
1/10+1/10×5/6+1/10×5/7+1/10×5/8+1/10×5/9=5/10×(1/5+1/6+1/7+1/8+1/9)
一般化して、最初にk枚捨てる場合の勝つ確率P(k)は、
P(k)=k/10×(1/k+1/(k+1)+1/(k+2)+・・・・+1/9)
kがいくつのときP(k)が最大になるかを調べると、
P(k+1)-P(k)=(1/(k+1)+1/(k+2)+・・・・+1/9-1)/10
なので、
1/4+1/5+1/6+1/7+1/8+1/9≒0.9956<1
1/3+1/4+1/5+1/6+1/7+1/8+1/9≒1.3289>1
より、k=3のとき最大になることが分かります。
よって、最善の戦略は、
最初に3枚のカードを捨てて、4枚目から最初に3枚のカードより大きかったらキープする。
おお!すばらしい。調和級数がでてくるのですね。ありがとうございます。
パソコンで順列を生成してシミュレーションした結果とぴったり一致しました。
また教えていただいた式でnを変えて計算してみると、
n=10 :k=3 P(k)=約0.399
n=100 :k=37 P(k)=約0.371
n=1000:k=368 P(k)=約0.368
n=2000:k=736 P(k)=約0.368
・・・となりました。
nをどんどん大きくしたらどうなるかは不明です。収束するようなしないような・・・
キープできる枚数が複数のときの戦略は方針さえまだ浮かんでおりません。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
高校数学です。 赤玉3個と白玉5...
-
確率は同じものを区別しないの...
-
数Aの問題です。 3つの箱A,B,C...
-
赤玉3個、白玉4個、青玉2個の入...
-
白玉5個、赤玉3個が入っている...
-
確率誰か教えてください。
-
【高校数学/確率】 袋の中に赤...
-
数学Aで質問です。 赤玉5個と白...
-
至急 数A 白玉3個、 赤玉2個, ...
-
Aの袋には赤玉3個と白玉6個が入...
-
数学A 確率 赤、青、黄、緑の4...
-
数学の期待値の問題で困ってい...
-
赤玉3個、白玉5個が入った袋か...
-
確率の問題 7枚のカードから3...
-
数学の問題がわかりません。 1...
-
サイコロを三つ同時に振るとき ...
-
確立の問題
-
確率
-
数A 赤玉5個と白玉10個が入って...
-
確率の問題(2)
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
高校数学です。 赤玉3個と白玉5...
-
【高校数学/確率】 袋の中に赤...
-
赤玉3個、白玉4個、青玉2個の入...
-
白玉5個、赤玉3個が入っている...
-
確率は同じものを区別しないの...
-
至急 数A 白玉3個、 赤玉2個, ...
-
確立の問題
-
3つのサイコロの和が3の倍数...
-
数学Aで質問です。 赤玉5個と白...
-
袋の中に赤玉六個、白玉3個がは...
-
数学の期待値の問題で困ってい...
-
数学A 確率 赤、青、黄、緑の4...
-
確率誰か教えてください。
-
確率の問題 赤玉5個、青玉4個、...
-
赤玉3個、白玉5個が入った袋か...
-
数学の確率を教えてください!
-
高校数学Aについての質問です。...
-
数A 赤玉5個と白玉10個が入って...
-
数Aの問題です。 3つの箱A,B,C...
-
数学の問題がわかりません。 1...
おすすめ情報