\(K\) が偶数であるという制約の導出です。

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

本ユーザー解説では、コマはマス間を移動するのではなく、隣接する格子点を\((1,1)\)から\((N,N)\)へ移動するとします。(後程ピックの定理を使う都合上です。)

公式解説同様に、右、左方向の移動回数をそれぞれ \(R\), \(L\) とします。

さらに、左右方向の移動のうち、奇数行で行われるものを合わせて \(H_o\) 回、偶数行で行われるものを \(H_e\) とします。

まず、

• \(H_o+H_e=R+L\)
• \(R-L=N-1\)

が簡単に分かります。

次に、

• \(H_o-H_e=N-1\)

が言えます。

証明

上下方向の移動を合わせて \(V\) 回とします。

各格子点を頂点、移動を辺としたグラフを考えたとき、奇数行にある格子点の次数の和は \(N(N+1)-2\) です。(格子点の数が \(\frac{N(N+1)}{2}\) で, \((1,1),(N,N)\) のみ次数が \(1\))

同様に、偶数行にある格子点の次数の和は \(N(N-1)\) です。

ここで、各辺の、奇数行の頂点の次数への寄与を考えることで、

• \(2H_o+V=N(N+1)-2\)

を得ます。同様に偶数行への寄与を考えると

• \(2H_e+V=N(N-1)\)

を得て、辺々を引くことで所望の式を得ます。

これと、冒頭で挙げた二式を合わせることで、\(H_o=R\) が分かります。

よって、 \(H_o\) が偶数であることが示せれば十分です。

ここで、移動経路を以下の通りに延長して移動を閉路にします。(直感的には、作った経路の左下部分をぐるりと回って元の(1,1)に帰ってきています)

\((1,1)\to\dots\to(N,N)\to(N+1,N)\to(N+1,N-1)\to\dots\to(N+1,0)\to(N,0)\to\dots\to(1,0)\to(1,1)\)

この閉路の周上の格子点の数を \(B\), 内部の面積を \(S\), 内部にある格子点の個数を \(I\) とすると、ピックの定理から

• \(2S=2I+B-2\)

です。さらに、今回の状況では \(I=0\), \(B=(N+1)^2\) が簡単に分かり、

• \(2S\equiv 2\pmod{4}\) \((\iff S\equiv 1\pmod{2})\)

となります。後は \(S\equiv H_o+1\pmod{2}\) を示せば証明は完了です。

\(i=1,2,\dots,N\) について、\(H(i)\coloneqq\{y\mid \text{閉路上で }(y,i-1)\to(y,i)\text{ か }(y,i)\to(y,i-1)\text{ に辺がある}\}\) とし、\(H(i)\) の元を値の大きい順に並べた列を \((y_{i,1},\dots,y_{i,2r_i})\) とします。(今閉路を考えているので\(H(i)\)の要素数は偶数です。)

すると、各列について、奇数番目の辺と偶数番目の辺の間が閉路の内部であることから求める面積は

\[S=\sum_{i=1}^{N}\sum_{j=1}^{r_i}y_{i,2j-1}-y_{i,2j}\]

です。特に、\(\mod{2}\)を考えると、

\[S\equiv\sum\sum y_{i,j}\equiv\#\{(i,j)\mid y_{i,j}\text{は奇数}\}\pmod{2}\]

です。経路を閉路にする際に新たに追加した辺のうち、奇数行の横移動にあたるのは \((1,0)\to(1,1)\) のみの丁度一本であることから、

\[S\equiv H_o+1\pmod{2}\]

を得て、\(R= H_o\equiv S-1\equiv 0\pmod{2}\) が従います。