\(N=2\) で実験をしてみます。\(0 \le A_1,A_2 < 20\) での実験結果が以下です。先手が勝てるならば \(1\)、そうでないならば \(0\) となっています。

01111111111111111111
11001111111111111111
10101111111111111111
10011111111111111111
11111111011101111111
11111111110011001111
11111111101010101111
11111111100110011111
11110111111101111111
11111100111111001111
11111010111110101111
11111001111110011111
11110111011111111111
11111100110011111111
11111010101011111111
11111001100111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111

フラクタル構造が見えます。ここから、\(4\) 進数などが条件に関与していそうだとなります。実際、この予想は正しいです。

上記で先手が敗北するためには、以下のいずれかを満たす必要があります。

• \(A_1,A_2\) が共に \(3\) 以下であり、 共に \(0\) か \(1\) 以上かつ異なる。
• \(A_1,A_2\) が共に \(4\) 以上であり、\(4\) で割った商が異なり、\(4\) で割ったあまりが共に \(0\) か \(1\) 以上かつ異なる。

\(A\) の要素を \(4\) 進数で見たときの表示で見ることにします。例えば、\(A=(5,8)\) ならば \(((1,1),(0,2))\) と見ます。この時、上記より \(N=2\) での勝利条件は以下と予想が立てられます。

• ある整数 \(j\) が存在し、「\(A_{1,j},A_{2,j}\) が片方のみ \(0\) であるか、両方 \(1\) 以上かつ一致している。」

これを証明しましょう。まず、勝利条件を満たしているならば勝利条件を満たさない盤面を相手に渡すことが出来ることを示します。以下、鍵括弧内部の条件を単に条件と呼ぶこととします。

条件を満たす \(j\) のうち、最大のものを持ってきます。このとき、以下のような非負整数 \(X\) で操作をすればよいです。

• \(0 < A_{1,j} = A_{2,j}\) のとき
  • \(k\) 桁目が条件を満たすとき、\(X\) の \(k\) 桁目は \(\max(A_{1,k},A_{2,k})\) とする。
  • \(k\) 桁目が条件を満たさないとき、\(X\) の \(k\) 桁目は \(0\) とする。
• \(0 = A_{1,j} < A_{2,j}\) のとき
  • \(k\) 桁目が条件を満たし、かつ \(0 < A_{1,k}=A_{2,k}\) のとき、\(X\) の \(k\) 桁目は \(0\) とする。
  • \(k\) 桁目が条件を満たし、かつ \(0 = A_{1,k}<A_{2,k}\) のとき、\(X\) の \(k\) 桁目は \(A_{2,k}\) とする。
  • \(k\) 桁目が条件を満たし、かつ \(0 = A_{2,k}<A_{1,k}\) のとき、\(X\) の \(k\) 桁目は \(0,A_{1,k}\) 以外とする。
  • \(k\) 桁目が条件を満たさないとき、\(X\) の \(k\) 桁目は \(0\) とする。

勝利条件を満たしていないならば、どのように操作をしても相手に勝利条件を満たす盤面を渡してしまうことを証明しましょう。\(X\) の最上桁を \(k\) 桁目とします。このとき、\((A_{1,k},A_{2,k})\) は \((0,0),(1,2),(2,3),(3,1)\) のいずれかとなりますが、ここに \(0,1,2,3\) のうち、操作を行えるいずれかで操作をしても必ず \(k\) 桁目が条件を満たしてしまうことが確認できます。

よって、\(N=2\) の勝利条件が上記であることが証明出来ました。そしてこの解法は以下のように拡張をすることで \(N\) が一般の時にも応用できます。

• ある整数 \(j\) が存在し、「\(A_{1,j},A_{2,j},\dots,A_{N,j}\) に登場する \(1,2,3\) の種類数はちょうど \(1\) 種類である。」

証明は上記を少し変えることで示せるため省略します。証明の際は、今まで違い、\(k\) 桁目に存在する整数の集合としてあり得るものが増えることに注意してください。

よって、上記を実装することによってこの問題を \(\mathrm{O}(N\log A)\) で解くことが出来ます。