MathDB

3

Part of 2023 Regional Olympiad of Mexico Southeast

Problems(1)

Connecting Black Cells

Source: Mathematics Regional Olympiad of Mexico Southeast 2023 P3

10/8/2023
Let nn be a positive integer. A grid of n×nn\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 kk colored cells, then k≥n2+2n3.k\geq \frac{n^2+2n}{3}.
gridColoring