\(N\) は奇数であるとします。

\(N\times N\) の各マス \((i,j)\) を、\(i+j\) が偶数なら黒で、奇数なら白で塗ることを考えます。各黒マスに \((i,j)\) の辞書順に \(1\) から \(\displaystyle\frac{N^2+1}2\) までの番号を付けます。白マスについても同様です。

また、\(N^2-1\) 回の移動で通ったマスを \((1,1)\) から順に \(\displaystyle v_1,v_2,\ldots,v_{N^2}\) とします。

\(\displaystyle i=1,2,\ldots,\frac{N^2-1}2\) に対し、マス \(v_{2i-1},v_{2i}\) にまたがるようにドミノを置くことを考えます。この \(\displaystyle \frac{N^2-1}2\) 個のドミノは互いに重ならず、\((N,N)\) 以外の全てのマスを覆います。また、このドミノの置き方を \(M\) として、\(i\) 番目の白マスを覆ったドミノが覆っている黒マスの番号を \(P_i\) としたときの \(P\) の転倒数を \(f(M)\) と書きます。

また、横に置かれたドミノであって左に黒マスがあるものの個数を \(g(M)\) と表記します。このとき、\(f(M)+g(M)\) の偶奇は \(M\) によらず一定です。

証明：

全てのドミノの敷き詰め方は、縦に並んだ \(2\) つの横に隣接しているドミノを横に並んだ \(2\) つの縦に隣接しているドミノに変える操作と、その逆の操作を行うことで互いに到達可能です。したがって、この \(2\) つの操作で \(f(M)+g(M)\) の偶奇が変わらないことを言えば良いです。

互いに到達可能であることの証明：

\(N\times N\) マスで \((N,N)\) が欠けているようなグリッドを考えます。

グリッドの辺に対して向きを付けます。具体的には、黒く塗られたマスの周りの \(4\) 辺を反時計回りに向きを付け、白く塗られたマスの周りの \(4\) 辺を時計回りに向きを付けます。

そして、グリッドの各格子点に重みを付けます。\((1,1)\) の左上の格子点の重みを \(0\) として、以下を満たすように格子点 \(x\) の重み \(h(x)\) を付けていきます。

• \(x\to y\) と向きのついた辺に対して、その辺を跨ぐようなドミノが存在する場合 \(h(y)-h(x)=3\) とし、そのようなドミノが存在しない場合 \(h(y)-h(x)=-1\) とする。

各マスはちょうど \(1\) 回ずつ覆われていることから、この定義は well-defined です。さらに、グリッドの境界の辺を跨ぐドミノは存在しないため、境界上の格子点の重みはドミノの敷き詰め方によらず一定です。

異なる \(2\) つの敷き詰め方 \(M,M'\) を考え、格子点 \(x\) の重みをそれぞれ \(h(x),h'(x)\) とします。さらに、\(d(x)=h(x)-h'(x)\) とします。

境界上の格子点について \(d(x)=0\) が成り立ち、さらに \(x\to y\) という辺に対し \(h(y)-h(x),h'(y)-h'(x)\) は \(-1,3\) のいずれかなので \(d(y)-d(x)\) は \(-4,0,4\) のいずれかです。これらを合わせると、\(d(x)\) は常に \(4\) の倍数であることが分かります。

\(M,M'\) は異なる敷き詰め方であるため、\(d(x)\neq 0\) となる \(x\) が必ず存在します。\(d(x) > 0\) であるような \(x\) の中で \(d(x)\) が最大のものを考え、そのような \(x\) が複数存在する場合は \(h(x)\) が最大となる \(x\) を一つ取ります。もしそのような \(x\) が存在しない場合、\(M\) と \(M'\) を swap することで同じ状況に帰着することができます。\(x\) はグリッド内部の格子点です。

\(x\) に隣接する格子点 \(y\) を \(1\) つ取ります（つまり、 \(x\to y\) または \(y\to x\) となる辺が存在する \(y\) を取る）。もし \(d(y)=d(x)\) である場合、\(x\) の選び方から \(h(y) < h(x)\) が成り立ちます。一方、\(d(y) < d(x)\) である場合、\(d\) は \(4\) の倍数なので \(d(y) \le d(x)-4\) となります。ここから \(h(y)-h(x) =h'(y)-h'(x)+d(y)-d(x) \le 3-4 < 0\) となり、この場合も \(h(y) < h(x)\) が成り立ちます。したがって、常に \(h(y) < h(x)\) が成り立ち、このことから \(h(x)\) は局所的に最大値であることが分かります。

\(h(x)\) が \(4\) 方向どこに進んでも下がるようにするためには、\(x\) に入る \(2\) 本の向かい合う辺それぞれを跨ぐドミノが存在する必要があります。これはすなわち \(x\) を中心とする \(2\times 2\) マスが \(2\) 本の並行なドミノで覆われているということです。この \(2\) 本を flip すると、\(d(x)\) のみ \(4\) 減少し、\(y\neq x\) に対し \(d(y)\) の値は変わりません。

したがって、この操作を繰り返すことで最終的に全ての \(x\) に対し \(d(x)=0\) となり、\(M\) と \(M'\) を一致させることができます。

これらの操作は \(f(M)\) の定義に使った順列に互換を作用させることに対応するので、\(f(M)\) の偶奇は必ず変わります。また、縦 \(2\) つを横 \(2\) つにすると \(g(M)\) は必ず \(1\) 増え、逆操作は必ず \(1\) 減るので \(g(M)\) の偶奇も必ず変わります。したがって、\(f(M)+g(M)\) の偶奇は常に一定です。

以上より偶奇が一定であると分かったので、次にその偶奇を求めます。

まず、ドミノの敷き詰め方 \(M\) として以下のようなものを考えます：

• \(\displaystyle i=1,2,\ldots,\frac{N-1}2,\) \(j=1,2,\ldots,N\) に対し、\((2i-1,j)\) と \((2i,j)\) に縦にドミノを置く。
• \(\displaystyle j=1,2,\ldots,\frac{N-1}2\) に対し、\((N,2j-1)\) と \((N,2j)\) に横にドミノを置く。

\(g(M)\) は簡単に計算でき、横に置かれたドミノは必ず左が黒マスなので \(\displaystyle g(M)=\frac{N-1}2\) です。

\(f(M)\) を計算するために、まず上 \(2\) 行に着目します。\(\displaystyle k\le \frac{N+1}2\) なら黒マス \(k\) は白マス \(\displaystyle k+\frac{N-1}2\) と対応し、\(\displaystyle k> \frac{N+1}2\) なら黒マス \(k\) は白マス \(\displaystyle k-\frac{N+1}2\) と対応します。したがって、上 \(2\) 行だけで黒マス \(1,2,\ldots,N\) と白マス \(1,2,\ldots,N\) が一対一に対応しており、これらの転倒数は \(\displaystyle \frac{N-1}2\times \frac{N+1}2\) です。この値は偶数なので、縦に置かれたドミノのみを考えた時の転倒数は必ず偶数です。横に置かれたドミノも置かれたドミノの白マスと黒マスの番号は同じなので、全体として \(f(M)\) も偶数です。

以上より、\(\displaystyle f(M)+g(M)\equiv \frac{N-1}2\bmod 2\) が分かりました。

同様に、\(\displaystyle i=1,2,\ldots,\frac{N^2-1}2\) に対しマス \(v_{2i},v_{2i+1}\) にまたがるようにドミノを置くことを考えます。この敷き詰め方は \((1,1)\) を除く全てのマスを覆いますが、そのような敷き詰め方 \(M'\) に対しても \(\displaystyle f(M')+g(M')\) の偶奇は一定です。\((N,N)\) を除いた上記の敷き詰め方を \(180\) 度回転させた敷き詰め方を考えることで、\(\displaystyle f(M')+g(M')\equiv 0\bmod 2\) が分かります。

ここで、経路 \(v\) のうち黒マスを順に \(\displaystyle a_1,a_2,\ldots,a_{\frac{N^2+1}2}\)、白マスを順に \(\displaystyle b_1,b_2,\ldots,b_{\frac{N^2-1}2}\) とします。

\(M\) の定義中の \(P\) において、\(\displaystyle P \circ b = a'\) （\(a'\)は \(a\) の末尾の項のみを取り除いた整数列）が成り立つため \(f(M) \equiv \text{inv}(a')+\text{inv}(b)\equiv \text{inv}(a)+\text{inv}(b) \bmod 2\) が成り立ちます。\(M'\) についても同様に \(f(M')\equiv \text{inv}(a)+\text{inv}(b) \bmod 2\) が成り立つため、\(f(M) \equiv f(M') \bmod 2\) です。したがって、\(\displaystyle g(M)+g(M') \equiv \frac{N-1}2 \bmod 2\) となります。

奇数回目に右へ移動した回数は \(g(M)\) と一致し、偶数回目に右へ移動した回数は \(M'\) の横に置かれたドミノの数を \(X\) として \(X-g(M')\) と一致します。

\(M'\) において奇数行目に横に置かれたドミノの本数を \(x\) 、偶数行目の本数を \(y\) とします。\((1,1)\) を除いて奇数行目のマスは偶数行目より \(N-1\) 個多いため、\(2x-2y=N-1\) より \(\displaystyle x-y=\frac{N-1}2\) が必要です。したがって、\(\displaystyle X=x+y\equiv \frac{N-1}2\bmod 2\) が得られます。

以上より、\(K\equiv g(M)+X-g(M')\equiv N-1\equiv 0 \bmod 2\) となり、\(K\) が偶数であるという条件が導出されました。