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.
Back to puzzles
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.