Show that fewer than N black cells can never turn a whole NxN grid black when each cell with at least 2...

logic/invariants/infected.checkerboard New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Show that fewer than N black cells can never turn a whole NxN grid black
when each cell with at least 2 black neighbors turns black.

Assume a NxN grid/matrix.  Cells can either be black or white.  A cell's
neighbors are the UP/DOWN/LEFT/RIGHT cells, i.e. 4 neighbors for cells
that are not on the border, 2 neighbors for the ones on the corners, and
3 neighbors for the rest.

RULE: If a cell has at least 2 black neighbors, it becomes black itself.

EXAMPLE: If you let all cells on the diagonal be black, and the rest
white, by applying the RULE repeatedly, the whole grid becomes black.
Hence, with N black cells the whole N*N matrix becomes black.

PUZZLE: Show that it is impossible to construct an NxN matrix with less
than N black cells, whose all cells can become black by repeatedly
applying RULE.

[ Editor: the first line is the editor's summary. ]

Show solution

This is the problem of The Infected Checkerboard, page 79 of Peter
Winkler, Mathematical Puzzles, AK Peters, 2004 - highly recommended.  He
says it appeared in the Soviet magazine KVANT around 1986.  The key is
to consider the perimeter of the black area.

Note that once a cell is black, there is no rule to un-black it.  Then
consider: Is there a way to invade a row that has no black cells in it
or on the far side?  Think about such things as:

XcX

Xc
X

XcX
X

X
XcX
X

Then think about this:

X
Xc
X

The c has only one black neighbour, not three.  Diagonals don't count.

Gerry says: "Perimeter."  Notice that the perimeter of the blackened
area remains constant, or decreases, after each application of the rule;
but it never increases.  Notice that the perimeter of the totally-
blackened grid is 4N.  Therefore, the perimeter of the initially
blackened area must be at least 4N.  Therefore, it must contain at least
N black cells.  Q.E.D.

More precisely, count the total number of edges between squares which
separate a black square from a white one, counting `squares' outside the
grid as white.  Given this, it is clear that the perimeter of a filled
grid is 4N: there are N edges along the top of the grid separating black
squares from white squares, N down the left, N down the right and N
along the bottom.  (Were you perhaps counting perimeter in _squares_
rather than edges between squares?)

Now every time you blacken a square which has k black neighbours, you
decrease the perimeter by k (since the k edges between the black
neighbours and this square previously counted towards the perimeter and
now do not) and increase it by 4-k (since the remaining edges of this
square were previously white/white and are now white/black).  Thus the
perimeter decreases overall by k-(4-k) = 2k-4, and since the rule states
that k >= 2, this is at least zero every time.  Hence, the perimeter can
at best remain constant and cannot increase.

[ Editor: the contributors are not named in the collected material,
  apart from "Gerry".  The grouping of the small diagrams above into
  separate examples is the editor's reading of the original, where they
  run together. ]