金貨が \(a\) 枚、銀貨が \(b\) 枚の状態を \((a,b)\) と表します。この状態のゲームの値 \(f(a,b)\) を求めることを考えます。

\(d=a-2b,\displaystyle c_n=\frac23\left(1-\left(-\frac12\right)^n\right)\) として、\(f(a,b)\) は以下のように計算できることが証明できます：

• \(d\le 0\) で \(d\) が偶数のとき：\(\displaystyle f(a,b)=\frac d2\)
• \(d\le 0\) で \(d\) が奇数のとき：\(\displaystyle f(a,b)=\frac{3-d}2\)
• \(d>0\) のとき：\(f(a,b)=c_d\)

以下で帰納的に証明していきます。

[1] \(a=0\) のとき

Bobが \(1\) 枚ずつ銀貨を取っていく行動が最適です。\(\displaystyle f(0,b)=-b=\frac d2\) となります。

[2] \(b=0\) のとき

\(f(0,0)=0,f(1,0)=1\) が成り立ちます。さらに、\(\displaystyle f(a,0)=\frac{f(a-1,0)+f(a-2,0)}2\) が成り立つことから \(\displaystyle f(a,0)=c_a\) が分かります。

[3] \(a,b>0\) のとき

\(a'\le a,b'\le b,(a',b') \neq (a,b)\) を満たす状態 \((a',b')\) に対し上記の命題が証明されているとします。

[3-1] \(d\geq 2\) のとき

金貨を \(a\) 枚から \(a'\) 枚に減らしたとすると、\(d'=a'-2b<d\) となり、\(d'\) と \(a'\) の偶奇は一致します。

Alice の手番の時、\(d'\) は偶数となります。\(d'<0\) なら\(\displaystyle f(a',b)=\frac{d'}2\le -1\) で、\(d'\geq 0\) なら \(f(a',b)=c_{d'}\) です。\(c_0 < c_2 < c_4 <\cdots\) より、Alice が遷移後のゲームの値を最大とするためには \(a'\) を最大とする着手が最適です。

Bob についても同様です。

次に、銀貨を取ることを考えます。銀貨は取れる手番の人が好きに取れるので、明らかに \(2\) 枚以上取る操作は損です。その時のゲームの値は \(f(a,b-1)=c_{d+2}\) となります。

以上より、\(f(a,b)\) は \(d\) が偶数なら \(f(a,b)=\lbrace c_{d-2} \ |\ c_{d+2}\rbrace=c_d\) 、\(d\) が奇数なら \(f(a,b)=\lbrace c_{d+2} \ |\ c_{d-2}\rbrace=c_d\) と計算できます。つまり、\(d\) の偶奇によらず \(f(a,b)=c_d\) が成立します。

[3-2] \(d=0\) のとき

\(a=2b\geq2\) です。

Alice は金貨を取ることしかできません。Alice が到達可能なゲームの値の最大値は金貨を \(2\) 枚取った時の \(-1\) です。

Bob は金貨を取るとゲームの値が \(2\) 以上になりますが、銀貨を \(1\) 枚取るとゲームの値が \(\displaystyle \frac12\) となりこれが最小です。

したがって、\(\displaystyle f(a,b)=\left\{-1 \,\middle|\, \frac{1}{2}\right\}=0\) となります。

[3-3] \(d=0\) のとき

\(a=2b+1\geq 3\) です。

[3-2] と同様の議論により、\(\displaystyle f(a,b)=\left\{\frac34 \,\middle|\, 2\right\}=1=c_1\) となります。

[3-4] \(d<0\) かつ \(d\) が偶数のとき

\(d=-2k\) \((k\geq 1)\) とします。

Alice は金貨を取ることしかできません。到達可能なゲームの値の最大値は金貨を \(2\) 枚取った時の \(\displaystyle \frac{d-2}2=-k-1\) です。

Bob が到達可能なゲームの値の最小値は銀貨を \(1\) 枚取った時の \(-k+1\) です。したがって、\(\displaystyle f(a,b)=\lbrace -k-1\ |\ -k+1\rbrace=-k=\frac d2\) が成り立ちます。

[3-5] \(d<0\) かつ \(d\) が奇数のとき

\(d=1-2k\) \((k\geq 1)\) とします。

[3-4] と同様の議論により、\(a=1\) なら \(\displaystyle f(1,b)=\lbrace k\ |\ \rbrace=k+1=\frac{3-d}2\) 、\(a>1\) なら \(\displaystyle f(a,b)=\lbrace k\ |\ k+2\rbrace=k+1=\frac{3-d}2\) となり、いずれの場合も \(\displaystyle f(a,b)=\frac{3-d}2\) が成り立ちます。

---

以上でゲームの値を求める公式が証明できました。

実装では指数の大きい項から順に処理することでゲームの値の総和が \(0\) より大きいか判定することができます。