Kvant Math Problem 530

Let each cell be represented by a variable in $\mathbb F_2$, where $1$ means black and $0$ means white.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m59s
Source on kvant.digital

Problem

On a rectangular sheet of graph paper, some cells are colored black. Then all cells of the sheet are recolored simultaneously according to the following rule: a cell that had an even number of black neighbors becomes white, while a cell that had an odd number of black neighbors becomes black. (Neighbors are cells that share a side.)

  1. Prove that if the set $B$ of black cells remains unchanged under the recoloring (Fig. 1, a), then $B$ contains an even number of cells.
  2. Suppose that under the recoloring the set $B_1$ of black cells changes into $B_2$, $B_2$ into $B_3$, $\ldots$, $B_{r-1}$ into $B_r$, and $B_r$ back into $B_1$ (Fig. 1, b). Prove that the total number of black cells in the sets $B_1$, $B_2$, $\ldots$, $B_r$ is even.

Fig. 1

Fig. 1

R. Izmailov, 10th-grade student

Exploration

Let each cell be represented by a variable in $\mathbb F_2$, where $1$ means black and $0$ means white. The recoloring rule says that the new color of a cell is the parity of the number of black neighbors. Thus the transformation is linear over $\mathbb F_2$.

If $A$ is the adjacency matrix of the rectangular grid graph, and $x$ is the vector of colors, then one recoloring step is

$$x\mapsto Ax$$

over $\mathbb F_2$.

The first question asks about fixed points, namely vectors satisfying

$$Ax=x.$$

A parity statement about the number of black cells suggests summing all coordinates. Let $u$ be the all-ones vector. The parity of the number of black cells in a configuration $x$ is $u^Tx$.

For a fixed point,

$$u^Tx=u^TAx=(Au)^Tx,$$

because $A$ is symmetric.

The vector $Au$ contains, at each cell, the degree of that cell in the grid graph, reduced modulo $2$. Interior cells have degree $4$, edge cells degree $3$, corner cells degree $2$. Hence $Au$ is $1$ exactly on the non-corner boundary cells and $0$ elsewhere.

Then

$$u^Tx=(Au)^Tx$$

says that the parity of all black cells equals the parity of black boundary non-corner cells.

Using the fixed point equation itself, for a boundary non-corner cell $v$,

$$x_v=\sum_{w\sim v}x_w.$$

Summing this over all such boundary cells may produce cancellation. Compute modulo $2$. Every cell contributes as many times as it is adjacent to boundary non-corner cells. Interior cells contribute $0$ or $2$ times. Corner cells contribute once. Boundary non-corner cells contribute twice. Thus only the four corner cells survive. Therefore the parity of boundary non-corner black cells equals the parity of corner black cells.

Now sum the fixed point equation over the four corners. Each corner has two neighbors. Every boundary non-corner cell adjacent to a corner appears once; all other cells appear an even number of times. Hence the parity of corner black cells equals the parity of the six boundary cells adjacent to corners. Summing the fixed point equation over those six cells gives zero parity. This looks cumbersome.

A cleaner route is linear algebra. Since $A$ is symmetric,

$$\ker(A-I)$$

is orthogonal to

$$\operatorname{Im}(A-I).$$

If the all-ones vector $u$ belongs to $\operatorname{Im}(A-I)$, then every fixed point $x$ satisfies $u^Tx=0$, which is exactly the desired parity statement.

So the crucial question is whether

$$u\in\operatorname{Im}(A-I).$$

Let $b=Au+u$. Since $Au$ is $1$ on the non-corner boundary cells, $b$ is $1$ on all cells except those boundary non-corner cells. Try to solve $(A-I)y=u$ explicitly instead.

A more conceptual approach is to consider the cycle statement first. If

$$B_1\to B_2\to\cdots\to B_r\to B_1,$$

then with vectors

$$x_{i+1}=Ax_i,\qquad A^r x_1=x_1.$$

The total parity equals

$$u^T(x_1+\cdots+x_r).$$

Let

$$s=x_1+\cdots+x_r.$$

Then

$$As=s,$$

because cyclically permuting the terms leaves the sum unchanged. Thus $s$ is a fixed point. If part 1 proves every fixed point has even parity, then

$$u^Ts=0,$$

which is exactly the parity of the total number of black cells across all $B_i$.

Hence everything reduces to proving that every fixed point has even parity.

The most likely hidden error is the parity count obtained by summing fixed point equations over selected boundary cells. A cleaner invariant is preferable.

Let $y$ be the checkerboard coloring vector: $y_v=1$ on one bipartition class, $0$ on the other. Then for every cell,

$$(Ay)_v=\deg(v)\pmod 2.$$

Since degrees are odd exactly at non-corner boundary cells,

$$(A-I)y$$

equals the all-ones vector. Indeed, on interior cells and corners, $\deg(v)$ is even, so $(A-I)y=0-y=1$ if $y=1$? This is not uniform. The computation depends on the bipartition value, so this guess fails.

Try instead the all-ones vector $u$:

$$(A-I)u=Au+u.$$

This equals $1$ on interiors and corners, $0$ on boundary non-corners. Repeating with a vector supported on the boundary may generate $u$. There should be an explicit solution. Let $y$ be the indicator of all boundary cells. Then $(A-I)y$ equals $1$ on boundary non-corners and $0$ elsewhere after checking modulo $2$. Consequently,

$$(A-I)(u+y)=u.$$

This gives exactly what is needed.

Problem Understanding

This is a Type B problem.

A configuration of black cells is represented by a subset of the cells of a rectangular grid. Recoloring replaces each cell by the parity of the number of black neighboring cells. We must prove two parity statements.

The core difficulty is to recognize that the recoloring rule is linear over the field $\mathbb F_2$ and to connect parity of the number of black cells with orthogonality in that vector space.

The first part asks for fixed points of the recoloring map. The second part concerns periodic orbits. The second statement should follow from the first once the sum of all configurations in a cycle is observed to be a fixed point.

Proof Architecture

Let $A$ be the adjacency matrix of the rectangular grid graph over $\mathbb F_2$.

The first lemma states that recoloring is the linear transformation $x\mapsto Ax$, because the new color of each cell is the parity of the colors of its neighbors.

The second lemma states that if $y$ is the indicator vector of all boundary cells and $u$ is the all-ones vector, then $(A-I)(u+y)=u$.

The reason is that $(A-I)u$ is $1$ on interiors and corners and $0$ on boundary non-corner cells, while $(A-I)y$ is $0$ on interiors and corners and $1$ on boundary non-corner cells.

The third lemma states that every fixed point $x$ satisfies $u^Tx=0$.

The reason is that $x\in\ker(A-I)$, the matrix $A-I$ is symmetric, and $u\in\operatorname{Im}(A-I)$.

The fourth lemma states that if $x_1,\dots,x_r$ form a cycle, then $s=x_1+\cdots+x_r$ is a fixed point.

The reason is that $As=x_2+\cdots+x_r+x_1=s$.

The hardest step is the verification of the identity $(A-I)(u+y)=u$, because it requires a complete parity count for each type of cell.

Solution

Work over the field $\mathbb F_2$. Represent a coloring by a vector $x$, whose coordinate corresponding to a cell equals $1$ if the cell is black and $0$ otherwise.

Let $A$ be the adjacency matrix of the rectangular grid graph. For a cell $v$, the $v$th coordinate of $Ax$ is

$$(Ax)v=\sum{w\sim v}x_w,$$

where the sum is taken modulo $2$. This is precisely the parity of the number of black neighbors of $v$. Hence one recoloring step is the linear transformation

$$x\longmapsto Ax.$$

Let $u$ denote the all-ones vector. The parity of the number of black cells in a configuration $x$ is

$$u^Tx.$$

We first prove part $1$.

Let $y$ be the indicator vector of the boundary cells of the rectangle.

Consider $(A-I)u$. A cell contributes $1$ to this vector exactly when its degree in the grid graph is odd. Interior cells have degree $4$, corner cells degree $2$, and boundary non-corner cells degree $3$. Therefore

$$(A-I)u$$

equals $1$ on interior cells and corners, and equals $0$ on boundary non-corner cells.

Next consider $(A-I)y$.

If a cell is interior, then $y$ is $0$ on that cell and on either $0$ or $2$ of its neighbors, so the corresponding coordinate of $(A-I)y$ is $0$.

If a cell is a corner, then $y$ is $1$ on that cell and on its two neighbors, both of which are boundary cells. Hence the corresponding coordinate is

$$1+1+1=1$$

modulo $2$, which equals $0$.

If a cell is a boundary non-corner cell, then $y$ is $1$ on that cell. Among its three neighbors, exactly two are boundary cells. Hence the corresponding coordinate is

$$1+1+1=1$$

modulo $2$.

Thus $(A-I)y$ equals $1$ on boundary non-corner cells and equals $0$ elsewhere.

Adding the two descriptions gives

$$(A-I)(u+y)=u.$$

Hence

$$u\in\operatorname{Im}(A-I).$$

Now let $x$ be a fixed point. Then

$$(A-I)x=0.$$

Since $A-I$ is symmetric,

$$\ker(A-I)$$

is orthogonal to

$$\operatorname{Im}(A-I).$$

Because $u\in\operatorname{Im}(A-I)$, we obtain

$$u^Tx=0.$$

The left-hand side is the parity of the number of black cells in the fixed configuration. Therefore every fixed configuration contains an even number of black cells.

For part $2$, let

$$x_1,x_2,\dots,x_r$$

be the vectors corresponding to

$$B_1,B_2,\dots,B_r,$$

with

$$x_{i+1}=Ax_i$$

for $1\le i<r$ and

$$x_1=Ax_r.$$

Define

$$s=x_1+x_2+\cdots+x_r.$$

Then

$$As=Ax_1+\cdots+Ax_r =x_2+\cdots+x_r+x_1 =s.$$

Thus $s$ is a fixed point of the recoloring transformation.

By the first part,

$$u^Ts=0.$$

Since

$$u^Ts =u^T(x_1+\cdots+x_r) =u^Tx_1+\cdots+u^Tx_r,$$

the quantity $u^Ts$ is exactly the parity of the total number of black cells occurring in all sets

$$B_1,B_2,\dots,B_r.$$

Hence that total number is even.

This completes the proof.

∎

Verification of Key Steps

The identity $(A-I)(u+y)=u$ requires checking every possible type of cell.

For an interior cell, $(A-I)u=1$ because its degree is $4$, and $(A-I)y=0$ because it has either $0$ or $2$ boundary neighbors. The sum is $1$.

For a corner cell, $(A-I)u=1$ because its degree is $2$, and $(A-I)y=0$ because the corner and its two neighbors are all boundary cells. The sum is again $1$.

For a boundary non-corner cell, $(A-I)u=0$ because its degree is $3$, and $(A-I)y=1$ because the cell and its two boundary neighbors contribute three ones. The sum is again $1$.

A careless argument could overlook the corner case, where the parity differs from that of ordinary boundary cells.

The orthogonality step uses symmetry. If $u=(A-I)z$ and $(A-I)x=0$, then

$$u^Tx=((A-I)z)^Tx =z^T(A-I)x =0.$$

Nothing beyond symmetry of $A-I$ is used. Forgetting to transpose would leave the argument incomplete.

For the cycle argument, the equality

$$As=s$$

depends on the cyclic condition $Ax_r=x_1$. Without that condition one would obtain

$$As=x_2+\cdots+x_r+Ax_r,$$

which need not equal $s$.

Alternative Approaches

A more combinatorial proof of part $1$ can be obtained by summing the fixed point equations over carefully chosen boundary cells and reducing everything to parity counts on the boundary. The argument eventually shows that the parity of all black cells must vanish. Such a proof avoids linear algebra but requires several separate parity computations and careful treatment of corner cells.

Another approach is to regard the recoloring rule as a linear cellular automaton on a finite graph. The first statement becomes a property of vectors in $\ker(A-I)$, while the second statement follows by summing all vectors in a periodic orbit. This viewpoint isolates the structure responsible for both parity results and makes the proof of the second part almost immediate once the first part is established.