Let \(N\) be an odd number.

Paint each cell \((i, j)\) \(N\times N\) black if \(i+j\) is even, and white if it is odd. Assign numbers from \(1\) through \(\displaystyle\frac{N^2+1}2\) to the black cells in lexicographical order of \((i,j)\), and to the white cells too.

Let \(\displaystyle v_1,v_2,\ldots,v_{N^2}\) be the cells visited by the \((N^2-1)\) moves, starting from \((1,1)\).

Consider a domino tiling containing a domino covering cells \(v_{2i-1}\) and \(v_{2i}\) for \(\displaystyle i=1,2,\ldots,\frac{N^2-1}2\). These \(\displaystyle \frac{N^2-1}2\) do not overlap with each other, and cover all cells except for \((N,N)\). For this arrangement of dominoes \(M\), let \(f(M)\) be the inversion number of \(P\), where \(P_i\) is the index of the black cell covered by the domino covering the \(i\)-th white cell.

Let \(g(M)\) be the number of horizontal dominoes that have a black cell to the left. We claim that the parity of \(f(M)+g(M)\) is independent of \(M\).

Proof:

Any arrangement of dominoes can be transformed from one to another by repeatedly replacing two horizontal dominoes adjacent vertically with two vertical dominoes adjacent horizontally, and vice versa. Thus, it is sufficient to assert that these two operations do not change the parity of \(f(M)+g(M)\).

Proof of the reachability:

Consider an \(N\times N\) grid lacking cell \((N,N)\).

Assign a direction to the edges of the grid. Specifically, assign counterclockwise directions to the four cells around a black cell, and clockwise around a white cell.

Also assign a weight to each lattice point of the grid, so that the weight of \((1,1)\) is \(0\), and the weight \(h(x)\) of a lattice point \(h(x)\) satisfies:

• For an edge directed \(x \to y\), let \(h(y)-h(x)=3\) if a domino is striding over the edge, and \(h(y)-h(x)=-1\) otherwise.

This definition is well-defined because every cell is covered exactly once. Moreover, the weight of the lattice points on the circumference is independent of the arrangement of the dominoes, because no domino strides over the circumference.

Consider two different arrangement \(M\) and \(M'\). Let \(h(x)\) and \(h'(x)\) be the weights of the lattice points. Moreover, let \(d(x)=h(x)-h'(x)\).

A lattice point on the circumference satisfies \(d(x) = 0\), and for any edge \(x\to y\), \(h(y)-h(x)\) and \(h'(y)-h'(x)\) are either \(-1\) or \(3\), so \(d(y)-d(x)\) is one of \(-4\), \(0\), and \(4\). Thus, \(d(x)\) turns out to be always a multiple of \(4\).

Since \(M\) and \(M'\) are different arrangements, there always exist \(x\) with \(d(x)\neq 0\). Take an \(x\) maximizing \(d(x)\) for those with \(d(x)>0\); if there are multiple such \(x\), take one maximizing \(h(x)\). If there is no such \(x\), swapping \(M\) and \(M'\) leads to the same discussion. \(x\) is a lattice point inside the interior of the grid.

Take one lattice point \(y\) adjacent to \(x\) (in other words, take a \(y\) for which there exists an edge \(x\to y\) or \(y\to x\)). If \(d(y)=d(x)\), then the choice of \(x\) guarantees \(h(y) < h(x)\). If \(d(y) < d(x)\), then \(d(y) \le d(x)-4\) because \(d\) is a multiple of \(4\). This means \(h(y)-h(x) =h'(y)-h'(x)+d(y)-d(x) \le 3-4 < 0\), which again implies \(h(y) < h(x)\). In any case \(h(y) < h(x)\), so \(h(x)\) is locally maximum.

Advancing in any of the four directions decreases \(h(x)\), implying that the each of the two edges, pointing \(x\) and facing each other, must have a domino striding over. In other words, the \(2\times 2\) region centered at \(x\) is covered by two parallel dominoes. Flipping these two dominoes decreases \(d(x)\) by four, without changing \(d(y)\) for \(y\neq x\).

Hence, repeating this operation eventually makes \(d(x) = 0\) for all \(x\), making \(M\) match \(M'\).

These operations applies a transposition to the permutation used in the definition of \(f(M)\), always flipping the parity of \(f(M)\). Turning two vertical dominoes into two horizontals increases \(g(M)\) by \(1\), and the reverse decreases it by \(1\), changing the parity of \(f(M)\) and \(g(M)\). Thus, the parity of \(f(M)\) and \(g(M)\) remains invariant.

Now that we saw that the parity is an invariant, we will now find what the parity is.

First, consider a domino tailing \(M\) containing:

• vertical dominoes covering \((2i-1,j)\) and \((2i,j)\), for each \(\displaystyle i=1,2,\ldots,\frac{N-1}2\) and \(j=1,2,\ldots,N\); and
• horizontal dominoes covering \((N,2j-1)\) and \((N,2j)\), for each \(\displaystyle j=1,2,\ldots,\frac{N-1}2\).

It is easy to find \(g(M)\); indeed, \(\displaystyle g(M)=\frac{N-1}2\) because any horizontal domino has a black cell to the left.

To compute \(f(M)\), we will first focus on the top two rows. For \(\displaystyle k\le \frac{N+1}2\), the black cell \(k\) corresponds to the white cell \(\displaystyle k+\frac{N-1}2\); for \(\displaystyle k> \frac{N+1}2\), the black cell \(k\) corresponds to the white cell \(\displaystyle k-\frac{N+1}2\). Hence, the top two rows have a one-two-one correspondence between the black cells \(1,2,\ldots,N\) and the white cells \(1,2,\ldots,N\), for which the inversion number is \(\displaystyle \frac{N-1}2\times \frac{N+1}2\). This is even, so the inversion number contributed by the vertical dominoes is always even. Each horizontal domino covers a white cell and black cell with the same index, so \(f(M)\) is always even.

Hence, \(\displaystyle f(M)+g(M)\equiv \frac{N-1}2\bmod 2\).

Likewise a domino tiling containing a domino covering cells \(v_{2i}\) and \(v_{2i+1}\) for \(\displaystyle i=1,2,\ldots,\frac{N^2-1}2\). These dominoes cover all cells except for \((1,1)\), and such an arrangement \(M'\) also have an invariant parity \(\displaystyle f(M')+g(M')\). Obtain a tiling by rotating by \(180\) degrees the arrangement covering all cells but \((N,N)\) as stated above, and that shows \(\displaystyle f(M')+g(M')\equiv 0\bmod 2\).

In the path \(v\), let \(\displaystyle a_1,a_2,\ldots,a_{\frac{N^2+1}2}\) be the black cells, and \(\displaystyle b_1,b_2,\ldots,b_{\frac{N^2-1}2}\) be the white cells, in the visited order.

The \(P\) in the definition of \(M\) satisfies \(\displaystyle P \circ b = a'\) (where \(a'\) is the sequence obtained by removing the last element from \(a\)), so \(f(M) \equiv \text{inv}(a')+\text{inv}(b)\equiv \text{inv}(a)+\text{inv}(b) \bmod 2\). Similarly, \(M'\) satisfies \(f(M')\equiv \text{inv}(a)+\text{inv}(b) \bmod 2\), so \(f(M) \equiv f(M') \bmod 2\). Thus, \(\displaystyle g(M)+g(M') \equiv \frac{N-1}2 \bmod 2\).

The number of moves to the right equals \(g(M)\), and the number of moves to the left equals \(X-g(M')\), where \(X\) is the number of horizontal dominoes in \(M'\).

Let \(x\) and \(y\) be the number of horizontal dominoes placed in an odd-indexed and even-indexed rows, respectively. Excluding \((1,1)\), there are \((N-1)\) more cells in odd-indexed rows than in even-indexed rows, so \(2x-2y=N-1\), mandating \(\displaystyle x-y=\frac{N-1}2\). Thus, we obtain \(\displaystyle X=x+y\equiv \frac{N-1}2\bmod 2\).

Hence, \(K\equiv g(M)+X-g(M')\equiv N-1\equiv 0 \bmod 2\), implying that \(K\) must be even.