最適戦略 超難問？

質問

次のようなゲームを考えます。
（１）10枚のカードに数値が書かれてあり、見えないようにして置かれています。
（２）書かれている数値は全て異なっていますが、連続しているわけでもなく、最大値も知らされていません。
（３）カードを1枚づつめくっていき、最大値であろうと思われるところで1枚キープできます。キープ宣言はめくった直後のカードについてのみできます。
（４）めくったカードの数値はもちろん記憶しておいてかまいません。（記録しておいてもOK)
（５）全てのカードをさらして、キープしていたカードが最大値なら勝利です。最大値でなければ負けです。
問題：勝利する確率を最大にする戦略を考えなさい。　結構難問です。答えがあるのかどうかも不明です。
とりあえず思いついた戦略：5枚とりあえずめくってみる。その中の最大値を記憶。6枚目から順にめくって記憶した最大値より大きかったらキープして終了。
こうすると、
a)前半5枚に最大値が入っていれば、負け　1/2
b)前半5枚に2番目に大きなカードが入っていて、後半5枚に最大値が入っていれば、勝ち　1/2 ｘ 1/2
c)前半5枚に3番目に大きなカードが入っており、後半5枚に最大値が2番目より先に入っていれば、勝ち
・・・うーむ難しい。
そもそもこんな考え方でよいのか？　何枚か捨ててその情報を頼りに後半勝負するしかないような？　5枚がよいのかどうか？
もともとの問題は、カードｎ枚でキープできるカードはｋ枚となっていますが、難しすぎるので10枚、1枚で限定しました。

回答No.3

nag0720 · ベストアンサー

キープが複数のときの戦略は、ご友人のほうがはるかにいいですね。

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

nag0720

＞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 に収束するのでしょう。

カードｎ枚でキープできるカードがｋ枚の場合を考えてみました。

戦略は、
はじめのｍ枚は見逃す。
ｍ＋１枚目からは、はじめのｍ枚のカードより大きかったらキープする。
１枚でもキープしたあとは、直前にキープした数より大きかったらさらにキープする。
これを、キープがｋ枚になるまで繰り返す。

この戦略で勝つ確率は、
最大値のカードがはじめのｍ枚に入っていたら、0
最大値のカードがｍ＋１～ｍ＋ｋ枚目に入っていたら、必ず選ばれるので、k/n
最大値のカードがｉ枚目（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

nag0720

古くからある「見合いの問題」や「海辺の美女問題」に似ていますが、最大値かどうかだけならこのゲームのほうが簡単でしょう。
キープできるカードが複数の場合は難しいでしょうが。

戦略としては、何枚か捨ててそのあとにそれより大きい数を選ぶという方法しかないように思います。

で、５枚捨てる場合の確率ですが、
もし最大値のカードが前半５枚に入っていたら勝つ確率は、0
最大値のカードが６枚目だったら、必ずそれが選ばれるので勝つ確率は、1/10
最大値のカードが７枚目だったら、はじめの６枚の中の最大値が前半５枚に入っていたら、７枚目が選ばれるので勝つ確率は、1/10×5/6
同様に、最大値のカードが８枚目だったら、それが選ばれるので勝つ確率は、1/10×5/7
最大値のカードが９枚目だったら、それが選ばれるので勝つ確率は、1/10×5/8
最大値のカードが１０枚目だったら、それが選ばれるので勝つ確率は、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のとき最大になることが分かります。

よって、最善の戦略は、
最初に３枚のカードを捨てて、４枚目から最初に３枚のカードより大きかったらキープする。

お礼

おお！すばらしい。調和級数がでてくるのですね。ありがとうございます。
パソコンで順列を生成してシミュレーションした結果とぴったり一致しました。
また教えていただいた式で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をどんどん大きくしたらどうなるかは不明です。収束するようなしないような・・・
キープできる枚数が複数のときの戦略は方針さえまだ浮かんでおりません。