Optimal checking on a checkered paper

50 Views Asked by At

On the checkered paper 30x30 cells we want to check cells in such manner, that every unchecked cell has at least two checked neighbors. Neighborhood is considered vertically, horizontally, diagonally, and if a cell is near the edge than we take the neighbor from another side of the paper. Thus every cell always has precisely 8 neighboring cells. The goal is to find the minimum amount of checked cells that are requided for this procedure.

I considered to check cells like this. Seems quite optimal but I can't prove it. seems optimal

1

There are 1 best solutions below

0
On BEST ANSWER

It seems that we need a bit stronger claim than that from Henning Makholm’s comment. Let $n$ be the total number of cells and $k$ of them are checked in such manner, that every unchecked cell has at least two checked neighbors. Then the number $N$ of pairs $(u,c)$ of neighboring cells such that $c$ is checked whereas $u$ is not, it at least $2(n-k)$. From an other hand, since each checked cell has at most $8$ unchecked neighbors, we have $N\le 8k$. Thus $2(n-k)\le 8k$, that is $k\ge n/5$.

Now if each unchecked cell has exactly two checked neighbors then $N=2(n-k)$ and if each checked cell has exactly $8$ unchecked neighbors then $N=8k$. So if both these conditions hold (this is the strengthening of the claim) then $2(n-k)=8k$, that is $k=n/5$.