２人でババ抜き

<問題>
AとBの二人がいます。
Aは1,2,3,4,5と書かれたカードを持っています(全部で5枚)。
Bは0,1,2,3,4,5と書かれたカードを持っています(全部で6枚)。

最初にAとBのどちらかが、相手のカードを1枚引きます。
もし、手元に同じ数字のカードが2枚あれば、その2枚のカードを捨てます。
次に先ほどカードを引いてなかった方が相手のカードを引きます。
そして、手元に同じ数字のカードが2枚あれば、その2枚のカードを捨てます。
これを交互に行っていき、最初に手持ちのカードがなくなった方が勝者とします。

最初にAがBの持っているカードを１枚引くのと、

最初にBがAの持っているカードを１枚引くのと、

どちらがAの勝算が高くなるでしょうか？

ただし、相手のカードをとるとき、どのカードも等しい確率で取るものとする。





-----------------------
解答は下にスクロールしたら出てきます。
スポンサードリンク

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

(ここでは、0はババ抜きで言うジョーカーである。)

<解答>
0のカードとその他にn枚のカードを持っている人が相手のカードを先に引いて
0のカードを最初に持っていた人が最終的に勝つ確率をJS(n)とする。

0のカードとその他にn枚のカードを持っている人が相手にカードを先に引かせて

0のカードを最初に持っていた人が最終的に勝つ確率をJA(n)とする。

0のカードを持っておらず、n枚のカードを持っている人が相手のカードを先に引いて

0のカードを最初に持ってない人が最終的に勝つ確率をNS(n)とする。

0のカードを持っておらず、n枚のカードを持っている人が相手にカードを先に引かせて

0のカードを最初に持ってない人が最終的に勝つ確率をNA(n)とする。

(ちなみに、Jはジョーカー(Joker)を持っている人、Nはジョーカーを持ってない(Nai)人、

Sは先に(Sakini)相手のカードをひく、Aは後で(Atode)相手のカードをひくを意味している。)

まず、JS(n)+NA(n)=1, JA(n)+NS(n)=1であることを証明する。

これは、0のカードを最初に持っている人が最終的に勝つ確率と

0のカードを最初に持ってない人が最終的に勝つ確率を合わせたら

1になることより自明。(ようは、Aが勝つ確率とBが勝つ確率を足したら1である。)

次に、JS(1)=0となることを証明する。
これも、 相手が1枚のカードしか持っておらず、そのカードを0を持っている人が
引いたら、相手はカードが必ずなくなって必ず勝ってしまうことより自明。

また、JS(n)+NA(n)=1より、NA(1)=1

次にJA(1)を求める。
0のカードを持っている人のカードを、0のカードを持ってない人に先に引かせると、
0のカードを持ってない人が、1/2の確率で0以外のカードを引く。
すると必ずペアを作るので、0のカードを持ってた方が必ず負ける。
また、1/2の確率で0のカードを引く。
すると、0のカードを先に持っていた人が最終的に勝つ確率はNS(1)となる。
(そりゃ、0を持っておらず、先に相手のカードを引く状態になっただけだからね)

JA(1)=1/2×NS(1)
JA(n)+NS(n)=1であったので、
JA(1)=1/2×(1-JA(1))
ゆえにJA(1)=1/3
ついでに、NS(1)=2/3

さらに、0のカード1枚とその他にn枚のカードから1枚のカードを引く時、
0のカードを引く確率を1/(1+n), 0以外のカードを引く確率をn/(n+1)となることを
考慮に入れて、JS(n),JA(n)を求めると、

JS(n)=JA(n-1)
JA(n)=1/(n+1) ×NS(n)+n/(n+1) ×JS(n-1)となる。

これを使うと、JS(2)=JA(1)=1/3となる。

さらに、上の漸化式を改良すると、(NS(n)=1-JA(n)であることも使って)
JS(n)=JA(n-1)=1/n ×(1-JA(n-1)) +(n-1)/n ×JS(n-2)=1/n ×(1-JS(n)) +(n-1)/n ×JS(n-2)

ゆえに、(n+1)JS(n) - (n-1)JS(n-2)=1となる。

nが奇数の時、
(n+1)JS(n) - (n-1)JS(n-2)=1, (n-1)JS(n-2) - (n-3)JS(n-4)=1,・・・・4JS(3)-2JS(1)=1
を左辺は左辺だけで足し合わせて、右辺は右辺だけで足し合わせると、
(n+1)JS(n)-2JS(1)=(n-1)/2
よってnが奇数の時、JS(1)=0であることを考慮に入れて、
JS(n)=(n-1)/{2(n+1)}

nが偶数の時も同様に、JS(2)=1/3であることを考慮に入れて、
JS(n)={(n-2)/2 + 1}/(n+1)=n/{2(n+1)}

JS(n)=JA(n-1)なので、JA(n)も求められる。

nが奇数の時、
JA(n)=(n+1)/{2(n+2)}
nが偶数の時、
JA(n)=n/{2(n+2)}

で、求めるのは、NS(n),NA(n)なので、
NS(n)=1-JA(n), NA(n)=1-JS(n)であることを考慮に入れて、
nが奇数のとき、
NS(n)=(n+3)/(2n+4)
NA(n)=(n+3)/(2n+2)
nが偶数のとき、
NS(n)=(n+4)/(2n+4)
NA(n)=(n+2)/(2n+2)

NS(5)=4/7,NA(5)=2/3となり、
NS(5)<NA(5)となる。

最初にBがAの持っているカードを１枚引く方がAが最終的に勝つ可能性が高い。

<解答終わり>

ちなみに最初に持っているカードが奇数枚か偶数枚かによって、
最初に相手のカードを引いた方が勝てるのか、もしくは、
最初に相手にカードを引かせる方が勝てるのかが変わってしまう。
ツイート
目次に戻る