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 7 March 2017.

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