次のようなゲームを考えます。
(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.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をどんどん大きくしたらどうなるかは不明です。収束するようなしないような・・・
キープできる枚数が複数のときの戦略は方針さえまだ浮かんでおりません。
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.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になるようです。
確率式まで求めていただいて恐縮です。
戦略は考えようでいくらでもありそうで最適なのを見つけるのは相当難しいですね。
最適であるとの証明もできそうもないし。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 数学A、確率の問題です。 nを4以上の自然数とする。数字の1からnが書かれたカードが1枚ずつ、合計n 3 2023/07/02 22:54
- 統計学 確率の問題です。 7 2022/05/07 01:08
- 小学校 小3の問題 1 2022/08/31 17:44
- Excel(エクセル) 図書カードの分配 7 2023/05/09 15:57
- 数学 数学A 確率 赤、青、黄、緑の4色のカードが5枚ずつあり、各色のカードに1から5までの数字が1つずつ 4 2023/04/21 10:06
- 数学 1から9の数字を書いたカードが一枚ずつある。これらの9枚のカードから同時に2枚を取り出し、数字の大き 5 2022/04/25 15:38
- 占い タロットカードを浄化していたら、引くように言われたので引いたのですが… 1 2022/09/02 06:32
- 日本語 箱の中に,1 と書かれたカードが 3 枚,2 と書かれたカードが 2 枚,0 と書かれた カ 4 2022/03/31 13:46
- 数学 「1~5の数字が書かれたカードが5枚ある。(すべてのカードには異なった数字が書かれている) この5枚 4 2023/02/16 11:22
- くじ・懸賞 ジャンボくじのネット購入 4 2022/12/09 14:53
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
【高校数学/確率】 袋の中に赤...
-
赤玉3個、白玉4個、青玉2個の入...
-
高校数学です。 赤玉3個と白玉5...
-
サイコロを三つ同時に振るとき ...
-
確率誰か教えてください。
-
白玉5個、赤玉3個が入っている...
-
確率
-
3つのサイコロの和が3の倍数...
-
袋Aには赤玉が2個、白玉が3個入...
-
確率の問題
-
確率は同じものを区別しないの...
-
トランプを・・確率
-
確率の問題が分かりません。 一...
-
至急 数A 白玉3個、 赤玉2個, ...
-
数Aの問題です。 3つの箱A,B,C...
-
条件付確率の問題ですー高校数学
-
数学A 確率 白玉5個、赤玉n個の...
-
1から5までの5枚のトランプをシ...
-
確率の達人お願いします
-
高校の先生に質問です。
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
高校数学です。 赤玉3個と白玉5...
-
【高校数学/確率】 袋の中に赤...
-
白玉5個、赤玉3個が入っている...
-
至急 数A 白玉3個、 赤玉2個, ...
-
赤玉3個、白玉4個、青玉2個の入...
-
確率誰か教えてください。
-
確率は同じものを区別しないの...
-
サイコロを三つ同時に振るとき ...
-
袋Aには赤玉が2個、白玉が3個入...
-
確率において【同時に取り出す...
-
数学Aで質問です。 赤玉5個と白...
-
確率で2つのサイコロの問題で ...
-
3つのサイコロの和が3の倍数...
-
確率
-
A、Bの二つの袋があり、Aには赤...
-
統計学の順列・組み合わせの問...
-
数学A 確率 赤、青、黄、緑の4...
-
確立の問題
-
確率の問題
-
確率の問題 赤玉5個、青玉4個、...
おすすめ情報