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
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
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.
| 64232964 |
