Let $n$ be an even positive integer. We say that two different cells of a $n \times n$ board are neighboring if they have a common side. Find the minimal number of cells on the $n \times n$ board that must be marked so that any cell (marked or not marked) has a marked neighboring cell.
================================
The answer is $n(n+2)/4$. Due to symmetry we show that for half of the board it takes $n(n+2)/8$ marked cells. It is not hard to use induction to see that $n(n+2)/8$ suffices. To see why we couldn't do any better, we tilt the board by 45 degrees and have rows of cells of lengths $$1,3,5,\dots,n-5,n-3,n-1,n-1,n-3,n-5,\dots,5,3,1.$$ We pick $1$ cell from row $1$, $3$ cells from row $3$, etc., and $2$ cells from the last row, $4$ cells from the 3rd last row, etc. such that no two picked cells have common neighbors. The number of picked cells is $$1+2+\dots+\frac{n}{2}=n(n+2)/8,$$so we need to mark at least $n(n+2)/4$ cells just to cover them.
No comments:
Post a Comment