MathDB

Let

n

be a positive integer. A grid of

n\times n

has some black-colored cells. Drini can color a cell if at least three cells that share a side with it are also colored black. Drini discovers that by repeating this process, all the cells in the grid can be colored. Prove that if there are initially

k

colored cells, then

k\geq \frac{n^2+2n}{3}.

Problem Statement