solution:


对棋盘和棋盘周围一圈的格子x定义如下量
Neib(x) =0 if x是黑格
Neib(x) =x周围邻接的黑格数 if x是白格或周围一圈

Sum=\sum_x Neib(x)
则有如下事实：
1，在演化过程中Sum不增
2，棋盘全涂满时，Sum=4*n
则显然k*4>=Sum ====> k>=n

Solution:

We first extend the chessboard grid one layer (the new layer wraps around the original chessboard)

Then we define the function for every grid x.

Neib(x)=0 if x is black

Neib(x)= number of black neighbors(top,bottom,left,right) if x is white or in the new layer.

Define Sum=\sum_x Neib(x)

Then we can easily prove the following fact:

1.Sum is nonincreasing..

2.When all grids of the chessboard are colored black, Sum=4*n

So 4*k>=4*n, thus k>=n