Mana Deal

魔法を放った後のMPが相手より多いことを勝ちとする。
魔法を放たなかった側が必ず勝つため、求める確率 $p_r$ は、Bobが先に $r+\frac12$ MP以上を持つ確率である。

BobのMPを状態にする

$r$ を固定し、$S=r+1$ とおく。魔法を放つ前の二人のMPの合計は常に $S$ なので、BobのMPを $x$ とすれば、AliceのMPは $S-x$ と決まる。

この状態からAliceが勝つ確率、すなわちBobが先に $S-\frac12$ MP以上を持つ確率を $F(x)$ とする。最初のBobのMPは1なので、求める確率は $p_r=F(1)$ である。

すでにゲームが終了している状態では、

$$F(x)=0\quad\left(0\le x\le\frac12\right),\qquad F(x)=1\quad\left(S-\frac12\le x\le S\right).$$

まだ終了していない状態では、次のじゃんけんについて場合分けする。

• Bobがじゃんけんに負けると、自分のMPの半分を渡すため、BobのMPは $x/2$ になる。
• Bobがじゃんけんに勝つと、AliceのMPの半分を受け取るため、BobのMPは $x+(S-x)/2=(S+x)/2$ になる。

それぞれの確率は $1/2$ なので、

$$F(x)=\frac12F\!\left(\frac{x}{2}\right) +\frac12F\!\left(\frac{S+x}{2}\right) \qquad\left(\frac12<x<S-\frac12\right).$$

特に $F(1/2)=0$ なので、

$$p_r=F(1)=\frac12F\!\left(\frac{S+1}{2}\right).$$

二人を入れ替えたときの対称性

二人の名前を入れ替えてもルールは変わらないので、BobのMPが$x$の状態でAliceが先に魔法を放つ確率は$F(S-x)$である。確率1でどちらかが魔法を放つことと合わせると、

$$F(x)+F(S-x)=1.$$

特に、$x=(S+1)/2$とすると、

$$F\!\left(\frac{S+1}{2}\right) +F\!\left(\frac{S-1}{2}\right)=1.$$

よって、先ほどの$p_r=\frac12F((S+1)/2)$は、

$$p_r=\frac14+\frac14\left\{ F\!\left(\frac{S+1}{2}\right) -F\!\left(\frac{S-1}{2}\right) \right\}$$

と書き直せる。あとは、Bobの最初のMPが$(S-1)/2$の場合と$(S+1)/2$の場合で、Aliceが勝つ確率がどれだけ違うかを求めればよい。

同じじゃんけんの勝敗列で二つのゲームを比べる

$S=2$では対称性から$p_1=1/2$なので、以下では$S\ge3$とする。

Bobの初期MPが$(S-1)/2$のゲームと$(S+1)/2$のゲームを、同じじゃんけんの勝敗列で進める。どちらの更新もMPの大小関係を保つので、Bobの初期MPが少ないゲームでAliceが勝つなら、多いゲームでもAliceが勝つ。したがって、

$$F\!\left(\frac{S+1}{2}\right) -F\!\left(\frac{S-1}{2}\right)$$

は、この二つのゲームで最終的な勝者が異なる確率に等しい。

両方のゲームが続いている間、MPの差は毎ターン半分になる。さらに、$t$ターンの譲渡を行った直後の二つのMPは、ある正の奇数$q$を使って

$$L_t=\frac{qS-1}{2^{t+1}},\qquad U_t=\frac{qS+1}{2^{t+1}}$$

と表せる。これは$t=0$では$q=1$であり、Bobがじゃんけんに負ければ$q$は変わらず、じゃんけんに勝てば$q$に$2^{t+1}$が加わることから分かる。

勝者が異なるためには、まず一方だけが終了するターンが必要である。BobのMPが少ないゲームだけがBobの勝ちで終了するとき、

$$L_t\le\frac12<U_t \quad\Longleftrightarrow\quad qS-1\le2^t<qS+1.$$

各値は整数なので、これは

$$2^t=qS-1\quad\text{または}\quad2^t=qS$$

を意味する。BobのMPが多いゲームだけがAliceの勝ちで終了する場合も、二人を入れ替えれば同じ条件になる。この場合の奇数は$q$の代わりに$2^{t+1}-q$である。

ここで$S$が偶数なら、$t\ge1$に対して$qS-1$は奇数なので$2^t=qS-1$は成立しない。また、$q$は正の奇数なので、$2^t=qS$が成立するのは$q=1$かつ$S=2^t$の場合だけである。

よって、$S$が偶数で2の冪でない場合、二つのゲームの勝者は一致し、$p_r=1/4$である。

$S$が奇数の場合の必要条件

$S\ge3$が奇数なら$2^t=qS$は成立しないので、一方だけが終了し得るターンは

$$2^t\equiv-1\pmod S$$

を満たすものに限られる。このような$t$が存在しなければ、二つのゲームの勝者は一致し、$p_r=1/4$である。

この条件を判定するため、$2^d\equiv1\pmod S$を満たす最小の正整数$d$を考える。

$2^t\equiv-1\pmod S$を満たす$t$があるなら、$t$を$d$で割った余り$u$も同じ合同式を満たす。$0<u<d$かつ$2^{2u}\equiv1\pmod S$より$d\mid2u$なので、$2u=d$である。したがって、そのような$t$が存在する条件は

$$d\text{が偶数、かつ }2^{d/2}\equiv-1\pmod S$$

である。 したがって、$d$が奇数の場合、または$d$が偶数でも$2^{d/2}\not\equiv-1\pmod S$の場合は、$p_r=1/4$と確定する。

実際に$d$を求めるには、オイラーの定理から$d\mid\varphi(S)$となることを使う。 まず候補を$D=\varphi(S)$とし、$\varphi(S)$の各素因数$\ell$について、$\ell\mid D$かつ$2^{D/\ell}\equiv1\pmod S$である間、$D$を$D/\ell$に置き換える。最後に残った$D$が$d$になる。

求めた$d$が奇数なら、$p_r=1/4$と確定する。$d$が偶数なら、同じ剰余累乗の方法で$v=2^{d/2}\bmod S$を計算し、$v\ne S-1$なら$p_r=1/4$と確定する。

残るのは、$d$が偶数かつ$2^{d/2}\equiv-1\pmod S$の場合である。$h=d/2$とおくと、該当するターンは

$$t=h,\ 3h,\ 5h,\ \ldots$$

に限られる。

整数の間では$F(x)$は一定

じゃんけんの勝敗列を固定する。Bobの初期MPを$x$とすると、$t\ge1$ターンの譲渡後のMPは、整数$K$を使って

$$\frac{x+KS}{2^t}$$

と表せる。この時点での終了条件を$x$について書くと、

$$x\le2^{t-1}-KS \quad\text{または}\quad x\ge2^tS-2^{t-1}-KS$$

となり、どちらの境界も整数である。したがって、まだ終了していない初期状態同士で$x$が同じ隣接整数間にあれば、終了するターンと勝者は変わらない。よって、$F(x)$は各区間$(k,k+1)\cap(1/2,S-1/2)$で一定である。

一方だけが終了した後の確率

$S$が奇数のとき、$1/2<x<1$なら、$S/2$と$(S+x)/2$はともに$((S-1)/2,(S+1)/2)$内にある。上の性質と対称性から、

$$F\!\left(\frac{S+x}{2}\right)=F\!\left(\frac S2\right)=\frac12.$$

また、$F(x/2)=0$なので、

$$F(x)=\frac14\qquad\left(\frac12<x<1\right).$$

この$F(x)=1/4$を、二つのゲームの比較に使う。$t\ge2$ターン目に、BobのMPが小さいゲームだけが初めて終了したとする。$S$が奇数なので、その条件は$2^t=qS-1$であり、二つのMPの式に代入すると、

$$L_t=\frac{qS-1}{2^{t+1}}=\frac12,\qquad U_t=\frac{qS+1}{2^{t+1}}=\frac12+2^{-t}.$$

BobのMPが$L_t$のゲームでは、AliceのMPが$S-1/2$なので、Aliceが魔法を放ち、Bobが勝つ。

BobのMPが$U_t$のゲームはまだ続いている。$1/2<U_t<1$なので、先ほど求めた式から、この状態からAliceが勝つ確率は$F(U_t)=1/4$である。

一つ目のゲームはBobの勝ちで終わっているため、二つ目でAliceが勝つ場合にだけ勝者が異なる。よって、この状態から二つのゲームの勝者が異なる確率は$1/4$である。BobのMPが大きいゲームだけが先に終了した場合も、対称性から同じ確率になる。

各ターンで一方だけが終了する確率

まず$S\ge5$とし、$2^h\equiv-1\pmod S$を満たす最小の正整数$h$がある場合を考える。このとき$h\ge2$である。

$i$ターン目にBobがじゃんけんに勝つとき$b_i=1$、負けるとき$b_i=0$とすると、$t$ターン分の譲渡の式に現れる$q$は

$$q=1+\sum_{i=1}^{t}b_i2^i$$

である。したがって、$1$以上$2^{t+1}-1$以下の奇数$q$と、長さ$t$のじゃんけんの勝敗列は一対一に対応する。

候補ターン$t=h,3h,5h,\ldots$を固定する。BobのMPが小さいゲームだけが終了する条件は

$$q=\frac{2^t+1}{S}$$

である。この値は上の範囲内の奇数なので、対応する勝敗列はちょうど一つある。

この列では、途中でどちらのゲームも終了していない。実際、$L_t=1/2$から譲渡を逆にたどると、直前のMPは現在のMPの2倍、またはそこから$S$を引いた値なので、$1\le s<t$における$L_s$は整数になる。譲渡の式はMPを$(0,S)$内に保つため、$1\le L_s\le S-1$である。$s\ge2$なら$U_s=L_s+2^{-s}$も$1/2<U_s<S-1/2$を満たす。初手についても、$S\ge5$なら

$$L_1\ge\frac{S-1}{4}>\frac12,\qquad U_1\le\frac{3S+1}{4}<S-\frac12$$

なので、両方ともゲームが続く。

よって、この勝敗列が起こる確率$2^{-t}$が、そのまま$t$ターン目に初めてBobのMPが小さいゲームだけが終了する確率になる。大きいゲームだけが終了する確率も同じなので、$t$ターン目に初めて一方だけが終了する確率は$2\cdot2^{-t}$である。

その後に二つのゲームの勝者が異なる確率は$1/4$だった。初めて一方だけが終了するターンは一つに定まるため、各ターンの寄与を足し合わせることができ、

$$\begin{aligned} F\!\left(\frac{S+1}{2}\right)-F\!\left(\frac{S-1}{2}\right) &=\sum_{j=0}^{\infty}2\cdot2^{-(2j+1)h}\cdot\frac14\\ &=\frac{2^{-h}}{2(1-2^{-2h})} =\frac{2^{h-1}}{2^{2h}-1}. \end{aligned}$$

これを$p_r$の式に代入すると、

$$p_r=\frac14+\frac{2^h}{8(2^{2h}-1)}.$$

$S=3$では、$F(1)=F(2)/2$と$F(1)+F(2)=1$から$p_2=F(1)=1/3$である。これは上の式に$h=1$を代入した値と一致するため、同じ式で計算できる。

$S$が2の冪の場合

$S=2^m\ge4$とする。一方だけが終了する条件$2^t=qS$は、$q$が奇数なので$t=m$、$q=1$のときだけ成立する。

$q=1$に対応するのは、Bobが最初から$m$回連続でじゃんけんに負ける列である。途中の$s<m$では

$$L_s=\frac{S-1}{2^{s+1}}\ge\frac{S-1}{S}>\frac12$$

であり、$U_s$も減少し続けるので、両方のゲームが$m$ターン目まで続く。対称な場合は、Bobが最初から$m$回連続でじゃんけんに勝つ列である。したがって、一方だけが終了する確率は$2\cdot2^{-m}=2/S$である。

Bobが$m$回連続でじゃんけんに負けた場合、その時点のMPは

$$L_m=\frac12-\frac1{2S},\qquad U_m=\frac12+\frac1{2S}.$$

BobのMPが$L_m$のゲームではAliceが魔法を放ち、Bobが勝つ。二つのゲームの勝者が異なる確率は、残ったゲームでAliceが勝つ確率$F(U_m)$である。

ここでは$F(U_m)=F(1)=p_r$となる。実際、偶数$S\ge4$では、初期MPが$1/2<x\le1$なら、初手でBobがじゃんけんに負けると終了し、勝つと継続する。また、2ターン目以降の終了条件の境界$2^{t-1}-KS$、$2^tS-2^{t-1}-KS$はすべて偶数なので、この範囲で初期MPを変えても終了するターンと勝者は変わらない。したがって、$F(x)=F(1)$は端点$x=1$を含むこの範囲全体で成立する。

対称な場合も勝者が異なる確率は$p_r$なので、

$$F\!\left(\frac{S+1}{2}\right)-F\!\left(\frac{S-1}{2}\right) =\frac2S p_r.$$

これを$p_r$の式に代入して解くと、

$$p_r=\frac14+\frac14\cdot\frac2S p_r \quad\Longrightarrow\quad p_r=\frac{S}{4S-2}.$$