このゲームにおいて、2 人は以下の行動をするのが最善です。

• 1 が残っているならばその中で最も左のものを、そうでなければ残っている 0 のなかで最も右のものを選ぶ。

この公式解説ではこのことの証明のみを書きます。問題の解法についてはスライドを参照してください。

Alice が上記の戦略を取ることが最善であることを証明する。Bob についても同様の議論が成り立つ。

以下では文字 \(s_x\) に印を付ける行動のことを単に \(x\) などと書く。文字列の大小は全て辞書順とする。また Alice は最後に得られる文字列を出来るだけ大きく、Bob は小さくするように行動するものとする。

以下の補題が成り立つ。証明は省略する。

• (補題) \(S\) を 0 と 1 からなる文字列とする。
  • \(S\) に含まれる 1 つの 0 を選んで削除し、別の 0 を元の位置よりも右側に挿入して出来る文字列を \(T\) とすると、\(S\leq T\) が成り立つ。
  • \(S\) に含まれる 1 つの 1 を選んで削除し、別の 1 を元の位置よりも左側に挿入して出来る文字列を \(T\) とすると、\(S\leq T\) が成り立つ。
  • \(S\) に含まれる 1 つの 0 を選んで削除し、別の 1 を任意の位置に挿入して出来る文字列を \(T\) とすると、\(S < T\) が成り立つ。

厳密な証明のために少し定義をする。

• (定義) (盤面) このゲームの盤面とは、文字列 \(S\) に対して、それぞれの文字に 1 個以下の印 (o または x) をつけたものであって、このゲームに出現しうるものことをいう。また印がついていない文字が 1 個以上存在する盤面を途中盤面とよぶ。

• (定義) (戦略) このゲームにおける戦略とは、途中盤面全体の集合から \(\{1,\dots,2N\}\) への写像 \(f\) であって、任意の途中盤面 \(B\) について、\(S\) の \(f(B)\) 文字目に印がついていないようなもののことをいう。

ゲーム内において、Alice が盤面 \(B\) で \(f(B)\) を選択し続けることを 「Alice が戦略 \(f\) に従って行動する」、「Alice が戦略 \(f\) を採用する」などと書く。Bob についても同様である。

• (定義) (結果) 盤面 \(B\) から Alice が戦略 \(f\)、Bob が戦略 \(g\) に従って行動した場合に最後に得られる長さ \(N\) の文字列を \(\mathrm{res}(B, f, g)\) と表す。

• (定義) (戦略の最適性)

  • 戦略 \(f^*\) が Alice にとって最適であるとは、以下を満たすことをいう。
    • 盤面 \(B\) と戦略 \(f\) に対し、\(\displaystyle {T(B, f) = \min_{g:戦略}}\mathrm{res}(B, f, g)\) と定める。
    • このとき、任意の盤面 \(B\) について \(\displaystyle T(B,f^*) = \max_f T(B,f)\) が成り立つ。
  • 戦略 \(g^*\) が Bob にとって最適であるとは、以下を満たすことをいう。
    • 盤面 \(B\) と戦略 \(g\) に対し、\(\displaystyle {U(B, g) = \max_{f:戦略}}\mathrm{res}(B, f, g)\) と定める。
    • このとき、任意の盤面 \(B\) について \(\displaystyle U(B,g^*) = \min_g U(B,g)\) が成り立つ。

文字列 \(S\) を用いるゲームの戦略であって、Alice にとって最適なものが存在する。それをひとつ固定して \(f\) とする。

ある盤面 \(B\) で Alice の手番だったとする。印が付いていない文字に 1 が含まれるならばその中で最も左側の位置の文字、そうでないならば 0 のうち最も右の文字が \(s_x\) であるとする。\(y:=f(B)\neq x\) であったと仮定して、\(x\) もまた最善手であることを示せばよい。\(s_x\) の決め方から、次のいずれかが成り立つ。(\(\star\))

• \(s_x = s_y =\)0\(,y<x\)
• \(s_x = s_y =\)1\(,x<y\)
• \(s_x =\)1\(, s_y =\)0

\(B\) で \(x\) を選んだ後に、Alice は自分の手番が回ってきたら以下の行動をとる:

• このときの盤面を \(C\) とする。
  • まだ \(s_y\) に印がついていない場合
    • \(C\) において \(s_x\) についている o の印を削除し、\(s_y\) に o をつけた盤面を \(C'\) として、\(z:=f(C')\) とする。
    • \(z = x\) ならば \(y\) を選択して手番を終了する。\(z\neq x\) ならば \(z\) を選択して手番を終了する。
  • \(s_y\) に x がついている場合
    • \(C\) において \(s_x\) についている o の印を x に、\(s_y\) についている x を o にそれぞれ変化させた盤面を \(C'\) とする。
    • \(f(C')\) を選択して手番を終了する。
  • \(s_y\) に o がついている場合
    • \(f(C)\) を選択して手番を終了する。

戦略 \(f\) から、この Alice の行動のように盤面 \(B\) 以降の選択のみを変更して得られる戦略を \(f'\) とする。特に \(f'(B) = x\neq f(B)=y\) である。\(f'\) の最適性を示せばよい。

\(g'\) を Bob の任意の戦略とする。Bob の戦略 \(g\) が存在して、以下が成り立つ (証明略)。

• \(T=\mathrm{res}(B, f, g), T'=\mathrm{res}(B, f', g')\) とする。次のいずれかが成り立つ。
  • \(T=T'\)
  • \(T\) から \(s_y\) を削除し、\(s_x\) を(もとの \(S\) の位置関係で)挿入すると \(T'\) になる。

(\(\star\)) と補題から、\(T'\geq T\) が成り立つ。 一方、\(T^* := \mathrm{res}(B, f, g^*)\) とすると、\(f, g^*\) の最適性から \(T\geq T^*\) が成り立つ。よって \(T'\geq T^*\) が成り立つ。これは、盤面 \(B\) から Alice が \(f'\) を採用した場合、Bob がどのような戦略をとったとしても最終的な結果が \(T^*\) 以上になることを意味する。よって Alice は盤面 \(B\) 以降において \(f\) の代わりに \(f'\) を採用することで損をしない。\(f\) は最適な戦略であったから、\(f'\) もまた最適な戦略である。(証明終)