MathDB

Let

n

be a positive integer. Initially, a

2n \times 2n

grid has

k

black cells and the rest white cells. The following two operations are allowed : (1) If a

2\times 2

square has exactly three black cells, the fourth is changed to a black cell; (2) If there are exactly two black cells in a

2 \times 2

square, the black cells are changed to white and white to black. Find the smallest positive integer

k

such that for any configuration of the

2n \times 2n

grid with

k

black cells, all cells can be black after a finite number of operations.

P24