Changing Colors

Richard Beigel

Here's a general solution to your first question. It is possible to obtain exactly one white square in an m×n grid iff m = 1 or n = 1.

Proof

The parity argument on your web page shows the following: in every 2×2 subgrid you always have an even number of white squares (operations on other rows and columns don't effect the subgrid). If you get exactly one white square in an m×n grid where m > 1 and n > 1, then consider a 2×2 subgrid containing it.

Here's a general solution to your conjecture. In an nxn grid it is impossible to obtain exactaly k white squares where 0 < k < n.

Lemma

Two adjacent rows are either identically or inversely colored.

Proof

This is true initially, and it is preserved by inverting a row or a column.

Proof of conjecture

If every row is entirely black then there are 0 white squares. So there is some row that contains a white square. If it is entirely white, then there are n white squares. Otherwise it contains m white squares where 1 ≤ m ≤ n - 1. The rows adjacent to it contain m or n-m white squares. Since 1 ≤ n - m ≤ n - 1, every row contains at least one white square.

In fact if the board contains a white square then it contains a white path from one edge to its opposite edge.

One other interesting observation. A coloring is reachable iff every 2×2 subrectangle contains an even number of white squares. The forward direction is proved by your parity argument. The converse follows from the fact that adjacent rows are either identical or complementary.