\(4\leq N\) の場合に、\(\sum A\) が偶数なら後手が、そうでないなら先手が勝つことを示します。

まず、集合 \(\bar{S}\) を 全体集合を \(\{1, 2, \dots , N\}\) としたときの \(S\) の補集合と定義します。

\(\sum A\) が偶数のとき、先手の人は、\(|S| = N - 2\) であるタイミングで以下を満たす必要があります。

• \(\bar{S} = \{a, b\}\) とすると、\(A_{a}, A_{b}\) の偶奇が異なる。

もし、\(|S| = N - 3\) のタイミングで後手の人に手番が回ると、後手の人は上の条件を満たさないように \(|S| = N - 2\) にするような選び方が必ず存在するため、先手の人が勝つには \(|S| = N - 4\) から \(|S| = N - 3\) に変化するときの操作を後手の人に行わせる必要があります。

その操作を後手の人に強制的にさせることができる条件は、 以下と同値です。

• \(|S|= N - 4\) のタイミングでの \(\sum_{a \in \bar{S}} A_{a}\) が奇数

この条件は、\(a\in \bar{S}\) かつ、\(A_{a}\) が奇数であるようなものが \(1\) つもしくは \(3\) つであることと同値です。よって、後手の人は、奇数が \(1\) つならそれを、 \(3\) つなら偶数のものを選べば勝つことができます。

よって、\(4\leq N\) かつ \(\sum A\) が偶数ならば、後手が必ず勝つことができます。

全く同じ議論で、 \(4\leq N\) かつ \(\sum A\) が奇数ならば先手が必ず勝つことが証明できます。

おまけ

\(N = 1\) のときは先手必勝です。

\(N = 2\) であるときは後手が先手と異なるものを選べば勝ちです。

\(N = 3\) のときは、自分のターンで \(|S| = 2\) したら負けなので、先手が最初に選んだものを選び続けるのが最適になります。よって、先手は \(A_{i}\) が奇数である \(i\) を選べば勝つことができます。よって、\(A\) に奇数が含まれていることと先手必勝であることが同値です。