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 <= 4k and the final perimeter is 2m + 2n, 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