\((1,1)\) から \((N,N)\) まで \(4\) 方向の移動で到達するような経路を \(1\) つ取ります。これは蛇腹に移動すれば良いです。その経路で \(k\) 番目に通ったマスを \(v_k\) とします。

[1] \(N\) が偶数のとき

先手に必勝法が存在します。

\(\displaystyle k=1,2,\ldots,\frac{N^2-1}2\) に対し \(v_{2k-1}\) と \(v_{2k}\) をマッチさせるマッチングを考えます。マッチングされたペア同士は上下左右に移動することで互いに到達可能です。

先手は今いるマスとマッチングされたマスに移動する行動を行い続ければ良いです。

[2] \(N\) が奇数のとき

[2-1] \(A+B\) が偶数のとき

後手に必勝法が存在します。

\((A,B)\) が \(v_K\) であるとすると、parity から \(K\) は奇数になります。したがって、\(v_1\) から \(v_{K-1}\) 、\(v_{K+1}\) から \(v_{N^2}\) の隣接 \(2\) マスをそれぞれマッチさせることで [1] と同じことができます。

[2-2] \(A+B\) が奇数のとき

先手に必勝法が存在します。

\((N,N)\) を除いた \(N^2-1\) マスのマッチングを考え、同じことをすれば良いです。

このように先手が行動した場合、先手は \((N,N)\) へ移動しないこと、後手は parity から \((N,N)\) に移動できないことからこの戦法が必勝法であることが証明できます。