#5 Invariants II and Monovariants

In one move, the number of black coins either increases by \(2\), decreases by \(2\), or stays the same. Therefore its parity is preserved.

Initially the number of black coins is \(1\), which is odd. In the target position it is \(0\), which is even. The invariant values differ, so the position is unreachable.

Under chessboard colouring, each \(1\times2\) domino covers one black and one white square. Therefore any region tiled by dominoes contains equal numbers of black and white squares.

The full \(8\times8\) board has equal numbers of black and white squares. Removing two squares of the same colour destroys this equality. Hence a domino tiling is impossible.

Interpret \(+\) as \(1\) and \(-\) as \(-1\). One move changes two signs, so the product of the three numbers is multiplied by \((-1)^2=1\).

Initially the product is \(1\). For the state \(-,-,-\), the product is \(-1\). The invariant differs, so the state is impossible.

Each move changes the coordinate by a multiple of \(5\). Therefore the coordinate modulo \(5\) is invariant.

The initial coordinate has residue \(0\), while \(2026\equiv 1\pmod 5\). Hence point \(2026\) is unreachable.

After the move, the pile sizes become \(a-1\) and \(b+1\). The difference between the old and new sums of squares is

\[a^2+b^2-(a-1)^2-(b+1)^2=2(a-b-1).\]

Since \(a\ge b+2\), the right-hand side is positive. Therefore the sum of squares strictly decreases.

Let the numbers of red, blue, and green stones be \(r,b,g\). In a move, for example, \(r\) and \(b\) decrease by \(1\), while \(g\) increases by \(2\). The difference \(r-b\) is unchanged, while \(b-g\) and \(g-r\) change by multiples of \(3\). Therefore all pairwise differences modulo \(3\) are invariant.

Initially \(r-b=20-21=-1\), so \(r-b\equiv 2\pmod 3\). If all stones became one colour, then two of \(r,b,g\) would be \(0\), and the third would be \(63\), so all differences would be divisible by \(3\). Contradiction.

When \((a,b)\) is replaced by \((a-b,b)\) for \(a\ge b\), the gcd does not change: \(\gcd(a,b)=\gcd(a-b,b)\). The same holds when \(b\) is replaced by \(b-a\).

Initially \(\gcd(84,30)=6\). The pair \(7,7\) has gcd \(7\). Since the gcd is invariant, this pair is unreachable.

One move changes exactly two signs, so the product of all signs is multiplied by \((-1)^2=1\). Therefore the product is an invariant.

Initially the product is \(-1\), because there is one negative sign. In the all-positive state, the product is \(1\). The invariant differs, so the state is unreachable.

Colour the board like a chessboard. Every knight move takes the knight to a square of the opposite colour.

If a path through all \(25\) squares were closed, it would form a cycle of odd length \(25\) with colours alternating. But a closed alternating cycle must have even length. Contradiction.

Consider the parity of the number of black cells in each row. One move affects two cells in one chosen row and two cells in another chosen row. Hence the parity in every row is preserved. Similarly, the parity in every column is preserved.

Initially all row and column parities are \(0\). If there is exactly one black cell, its row and its column have odd parity. This is impossible.

An inversion is a pair of numbers in which the larger one stands to the left of the smaller one. The number of inversions is a nonnegative integer.

Swapping a neighbouring wrong pair decreases the number of inversions by exactly \(1\): that pair stops being an inversion, and the relations of these two numbers with all other numbers do not change the total number of inversions.

Therefore the number of inversions strictly decreases and cannot decrease forever. The process terminates.

Let \(S\) be the sum of the indices of the cells containing stones, counting stones with multiplicity. Each move increases \(S\) by exactly \(1\).

If there are \(m\) stones, then \(S\le mn\), because no stone can go beyond the \(n\)-th cell. Thus \(S\) strictly increases but is bounded above. Infinitely many moves are impossible.

Necessity: one move changes two signs, so the parity of the number of negative signs is preserved. If in the end there are \(0\) negative signs, then initially their number must be even.

For sufficiency, take a spanning tree and choose a root. Process leaves other than the root. If a leaf has a minus sign, apply the move to the edge joining the leaf to its parent; the leaf becomes positive, while the parent changes sign. If the leaf is positive, do nothing. After that, the leaf need not be touched again.

This makes all vertices except possibly the root positive. The parity of the number of negative signs has been preserved, and at the final stage there are no negative signs outside the root. Therefore the root is also positive. Hence all signs can be made positive.

Number the rows \(1,\ldots,10\) and the columns \(1,\ldots,14\). Let black cells be those for which \(i+j\) is odd. Let \(x_{ij}\) be \(0\) or \(1\), indicating whether the cell is marked.

Modulo \(2\), the number of marked black cells is

\[\sum_{i,j}(i+j)x_{ij}=\sum_i i\sum_j x_{ij}+\sum_j j\sum_i x_{ij}.\]

In every row and every column the number of marks is odd, so each such sum is \(1\) modulo \(2\). Therefore the desired parity is

\[\sum_{i=1}^{10} i+\sum_{j=1}^{14} j=55+105=160\equiv 0\pmod 2.\]

Thus the number of marked black cells is even.

In the initial colouring, every row and every column contains \(0\) black cells, an even number.

One move chooses two rows and two columns. In each chosen row, exactly two cells change colour, so the parity of the number of black cells in that row is preserved. Other rows do not change. The same argument applies to columns.

Therefore after any number of moves, all rows and columns preserve parity \(0\).

Consider the sum of squares of all pile sizes. If a stone is moved from a pile of size \(a\) to a pile of size \(b\), where \(a\ge b+2\), then the contribution of these two piles changes from \(a^2+b^2\) to \((a-1)^2+(b+1)^2\). As computed, the old sum exceeds the new one by \(2(a-b-1)>0\).

The sum of squares is a nonnegative integer, so it cannot strictly decrease forever. The process terminates.

If in the final state two piles differed by at least \(2\), a move would still be allowed. Hence in the end any two pile sizes differ by at most \(1\).

The gcd of the pair does not change when \((a,b)\) is replaced by \((a-b,b)\) or \((a,b-a)\), because common divisors are preserved in both directions.

If the numbers are not equal, one move decreases the sum \(a+b\): the larger number is replaced by a positive smaller number. The sum is a positive integer, so the process cannot continue forever.

When no move remains, the numbers are equal; let the pair be \(c,c\). The gcd has been preserved throughout, so \(c=\gcd(c,c)=\gcd(a,b)=d\). Thus the final pair is \(d,d\).

Necessity: one move changes two cells in each of two neighbouring rows and two cells in each of two neighbouring columns. Therefore the parity of the number of black cells in every row and every column is preserved. Initially all these parities are \(0\).

For sufficiency, let the target colouring have even rows and columns. We construct it from the white board. For \(i=1,\ldots,m-1\) and \(j=1,\ldots,n-1\), scan cells from left to right and top to bottom. If the current cell \((i,j)\) differs from the target, apply the move to the \(2\times2\) block with top-left corner \((i,j)\). After that, cell \((i,j)\) matches the target, and later moves will not affect it, because they start no higher and no further left.

After this procedure, all cells outside the last row and last column match the target. It remains to check the last row and last column. In every row and column, the current board has even black parity, and so does the target board. Therefore in each almost completed row, the last cell is forced to match the target. Similarly, the cells of the last row match. Hence the whole colouring is reachable.

Number the rows \(1,\ldots,14\) and the columns \(1,\ldots,18\). Let white cells be those for which \(i+j\) is even. Let \(x_{ij}\) be the indicator of whether the cell is marked.

Modulo \(2\), the number of marked white cells is

\[\sum_{i,j}(1+i+j)x_{ij}.\]

Expanding modulo \(2\), we get

\[\sum_{i,j}x_{ij}+\sum_i i\sum_j x_{ij}+\sum_j j\sum_i x_{ij}.\]

The total number of marked cells has parity \(14\), because each of the \(14\) rows contains an odd number of marks; hence this contribution is \(0\). Row and column mark sums are odd, so the remaining value is

\[\sum_{i=1}^{14}i+\sum_{j=1}^{18}j=105+171=276\equiv0\pmod2.\]

Therefore the number of marked white cells is even.

Represent a cell colour by \(0\) for white and \(1\) for black. If rows are switched according to variables \(r_i\in\{0,1\}\) and columns according to variables \(c_j\in\{0,1\}\), then the colour of cell \((i,j)\) is \(r_i+c_j\pmod2\).

For the rectangle corners \((i,j),(i,l),(k,j),(k,l)\), the sum of colours is

\[(r_i+c_j)+(r_i+c_l)+(r_k+c_j)+(r_k+c_l)\equiv0\pmod2.\]

Thus the number of black corners is always even.

Now prove the converse. Let a colouring \(a_{ij}\) have this property. Set \(r_i=a_{i1}\) for every row and \(c_j=a_{1j}+a_{11}\) for every column. Applying the rectangle condition to rows \(1,i\) and columns \(1,j\), we get

\[a_{ij}+a_{i1}+a_{1j}+a_{11}\equiv0\pmod2.\]

Hence \(a_{ij}=r_i+c_j\pmod2\). Therefore it is enough to switch all rows with \(r_i=1\) and all columns with \(c_j=1\). The colouring is reachable.