Kvant Math Problem 1489

Verified: yes
Verdicts: PASS + PASS
Solve time: 14m54s
Source on kvant.digital

Problem

For which rectangles $m\times n$ on squared paper, whose cells contain zeros and ones, is it possible to obtain any arrangement from any other arrangement, if it is allowed to change the numbers simultaneously in each row, each column, and on every line parallel to the diagonals of the cells (in particular, in the corner cells)?

A. I. Galochkin

Exploration

Work over the vector space $\mathbb F_2^{mn}$ of all $0$-$1$ configurations on the $m\times n$ rectangle. Flipping a row, a column, or a diagonal parallel to the diagonals of the cells is addition modulo $2$ of the indicator vector of that row, column, or diagonal.

Index rows by $i=0,\dots,m-1$ and columns by $j=0,\dots,n-1$. The diagonals parallel to the cell diagonals are exactly the sets with fixed value of $i+j$, so they are indexed by $k=0,\dots,m+n-2$.

If $r_i,c_j,d_k\in\mathbb F_2$ indicate whether the corresponding row, column, or diagonal is flipped, then the resulting configuration is

$$A(i,j)=r_i+c_j+d_{i+j}.$$

Hence the reachable configurations form the image of the linear map

$$T:(r,c,d)\longmapsto A,\qquad A(i,j)=r_i+c_j+d_{i+j}.$$

The problem asks for which pairs $(m,n)$ this map is surjective.

Problem Understanding

The parameter space has dimension

$$m+n+(m+n-1)=2m+2n-1.$$

To determine the rank, compute the kernel.

Suppose

$$r_i+c_j+d_{i+j}=0 \qquad\text{for all }i,j.$$

Assume first that $m,n\ge2$.

Putting $i=0$ gives

$$d_j=r_0+c_j \qquad (0\le j\le n-1).$$

Comparing the kernel equations for $(i,j)$ and $(i,j+1)$,

$$r_i+c_j+d_{i+j}=0, \qquad r_i+c_{j+1}+d_{i+j+1}=0,$$

yields

$$c_j+c_{j+1}=d_{i+j}+d_{i+j+1}.$$

The left side is independent of $i$, so there exists $\delta\in\mathbb F_2$ such that

$$d_t+d_{t+1}=\delta$$

for every admissible $t$.

Using $d_j=r_0+c_j$,

$$c_j+c_{j+1}=\delta$$

for all $j$.

Substituting $i=1$ into the kernel equation,

$$r_1+c_j+d_{j+1}=0,$$

and replacing $d_{j+1}$ by $r_0+c_{j+1}$ gives

$$r_1+r_0+c_j+c_{j+1}=0,$$

hence

$$r_1+r_0=\delta.$$

The same argument for any $i\ge1$ gives

$$r_i+r_0=\delta.$$

Thus

$$c_j=c_0+j\delta, \qquad r_i=r_0+\delta \quad (i\ge1).$$

Since $d_j=r_0+c_j$,

$$d_j=r_0+c_0+j\delta.$$

Now substitute these expressions into the kernel equation. For $i\ge1$,

$$\begin{aligned} r_i+c_j+d_{i+j} &=(r_0+\delta)+(c_0+j\delta) +(r_0+c_0+(i+j)\delta)\ &=(i+1)\delta. \end{aligned}$$

Therefore every kernel element must satisfy

$$(i+1)\delta=0 \qquad (i=1,\dots,m-1).$$

If $m\ge3$, taking $i=2$ gives

$$3\delta=\delta=0,$$

so $\delta=0$.

By symmetry, if $n\ge3$ then also $\delta=0$.

Hence whenever at least one of $m,n$ is at least $3$, every kernel element satisfies

$$\delta=0,$$

and therefore

$$r_i=a,\qquad c_j=b,\qquad d_k=a+b.$$

The kernel then has dimension $2$.

A different situation occurs when $m=n=2$. In that case there is no equation with $i=2$ or $j=2$, so $\delta$ may be either $0$ or $1$. The kernel is

$$r_i=a+i\delta,\qquad c_j=b+j\delta,\qquad d_k=a+b+k\delta,$$

which has dimension $3$.

The one-dimensional cases will be handled separately.

Proof Architecture

The classification follows from rank computations.

For rectangles with $m,n\ge2$ and at least one of them at least $3$,

$$\dim\ker T=2,$$

so

$$\operatorname{rank}T =(2m+2n-1)-2 =2m+2n-3.$$

For the special case $2\times2$,

$$\dim\ker T=3,$$

so

$$\operatorname{rank}T =7-3 =4.$$

The one-dimensional rectangles will be shown directly to be surjective.

After obtaining the necessary inequalities, explicit constructions will establish sufficiency.

Solution

First consider rectangles with $m,n\ge2$ and at least one of $m,n$ greater than $2$.

From the kernel computation,

$$\operatorname{rank}T=2m+2n-3.$$

If $T$ is surjective, then

$$2m+2n-3\ge mn.$$

Rearranging,

$$mn-2m-2n+4\le1,$$

or

$$(m-2)(n-2)\le1.$$

Among positive integers, the solutions are

$$m\le2, \qquad n\le2, \qquad \text{or} \qquad (m,n)=(3,3).$$

Since the formula above was derived only for boards other than $2\times2$, the case $2\times2$ must be checked separately. It is surjective because its rank equals

$$4=mn.$$

Thus the only candidates are

$$m\le2, \qquad n\le2, \qquad \text{or} \qquad (m,n)=(3,3).$$

It remains to prove that all of them work.

For $m=1$, every cell belongs to a unique diagonal. Given any target configuration $A(0,j)$, choose

$$d_j=A(0,j),$$

and all rows and columns equal to $0$. Then

$$A(0,j)=d_j.$$

Hence every configuration is reachable. The case $n=1$ is symmetric.

Now consider $m=2$. Given an arbitrary target configuration, solve

$$r_0+c_j+d_j=A(0,j),$$

$$r_1+c_j+d_{j+1}=A(1,j).$$

Choose

$$r_0=r_1=c_0=0.$$

Then

$$d_0=A(0,0), \qquad d_1=A(1,0).$$

Assume $d_j$ is known. Define

$$c_j=A(0,j)+d_j,$$

and then define

$$d_{j+1}=A(1,j)+c_j.$$

Proceeding successively determines all unknowns and satisfies every equation. Hence $T$ is surjective for every $2\times n$ rectangle. By symmetry, every $m\times2$ rectangle is also surjective.

Finally consider $3\times3$. Here

$$\operatorname{rank}T =2\cdot3+2\cdot3-3 =9.$$

Since the configuration space also has dimension

$$9,$$

the map is surjective.

Necessity has already been proved by the rank inequality, and sufficiency has been established for every remaining candidate.

Verification of Key Steps

For boards with $m,n\ge2$, the kernel equations imply

$$c_j=c_0+j\delta, \qquad r_i=r_0+\delta \ (i\ge1), \qquad d_k=r_0+c_0+k\delta.$$

If at least one dimension is at least $3$, substitution into the kernel equations forces

$$\delta=0.$$

Hence

$$\dim\ker T=2,$$

and

$$\operatorname{rank}T=2m+2n-3.$$

Surjectivity then requires

$$(m-2)(n-2)\le1.$$

The resulting candidates are

$$m\le2,\qquad n\le2,\qquad (m,n)=(3,3).$$

Every $1\times n$ and $n\times1$ rectangle is surjective directly. Every $2\times n$ and $n\times2$ rectangle is surjective by the recursive construction. For $3\times3$ the rank equals the full dimension of the configuration space.

Hence

$$\boxed{\text{Every configuration can be transformed into every other one} \iff m\le2\ \text{or}\ n\le2\ \text{or}\ (m,n)=(3,3).}$$

The critical error in the previous solution was the incorrect deduction $\delta=0$ from $\delta+\delta=0$ in $\mathbb F_2$. The correct argument is to substitute the general kernel form back into the kernel equations, obtaining $(i+1)\delta=0$. When a row index $i=2$ or a column index $j=2$ exists, this forces $\delta=0$. Only the exceptional case $2\times2$ retains the additional parity-pattern kernel direction. This corrected kernel computation restores the rank formula and the classification above.