Q: Consider a 10 x 10 array of white squares. Colour some initial
set black. Now, if a square has two black orthogonal neighbours, colour
it black. Repeat as much as possible. Show that if the initial set has 9
squares we cannot end with the whole array black.

Dima Fon-Der-Flaass, 24 Feb 1997

Q: More generally, find the minimum initial # blacks required to
turn an `m` x `n` array black.

A: ceil((`m` + `n`) / 2)

Necessity: The colouring process cannot increase the perimeter of the
black region Dima Fon-Der-Flaass. With `k` initial
blacks the initial perimeter is <= 4`k` and the final
perimeter is 2`m` + 2`n`, hence `k` >=
(`m` + `n`) / 2, and `k` is an integer, hence the
ceil( ).

Sufficiency: Wlog `m` (# rows) <= `n` (#
columns). Use `m` squares to colour the leading diagonal
black. Now start at the top right corner and work left along the top row
colouring alternate squares black, ending in either column `m`
+ 1 or `m` + 2. The diagonal will cause the left
`m` x `m` square to be blackened, and then the rest of
the array can be blackened in `m` x 2 strips seeded by the
squares in the top row.

This page is maintained by Thomas Bending,
and was last modified on Thu 28 July 2022.

Comments, criticisms and suggestions are welcome.
Copyright © Thomas Bending
2022