Some of the vertices of unit squares of an $n\times n$ chessboard are colored so that any $k\times k$ ( $1\le k\le n$) square consisting of these unit squares has a colored point on at least one of its sides. Let $l(n)$ denote the minimum number of colored points required to satisfy this condition. Prove that $\underset{n\to \infty }{\mathop \lim }\,\frac{l(n)}{{{n}^{2}}}=\frac{2}{7}$.
Problem
Source: Turkish NMO 1998, 6. Problem
Tags: limit, combinatorics proposed, combinatorics
11.08.2011 07:54
Lower Bound: $l(n) \ge \frac{2}{7}n^2 - O(n)$. Let $T$ be a set of marked cells with the desired property. Consider some $3\times n$ subgrid, with $r_1,r_2,r_3$ marked cells in rows 1,2 and 3 respectively. The $3\times n$ subgrid contains $2(n-1)$ subgrids of size $2\times 2$. We show that $2r_1+3r_2+2r_3 \ge 2(n-1)$. Any marked cell in rows 1 and 3 cover two $2\times 2$ grids (except at the edges of the board, but that effect is negligable as $n\to \infty$). So marked cells in rows 1 and 3 cover $2r_1+2r_3$ such grids. Any marked cell in row 2 covers four $2\times 2$ subgrids. However, a $3\times 3$ subgrid centered at a point, $x$ in row 2, must have a marked cell on its boundary. Therefore at least one of the $2\times 2$ subgrids covered by $x$ is also covered by another cell. So marked cells in row 2 cover at most $3r_2$ grids (not already covered by other cells) So all together we require $2r_1+3r_2+2r_3 \ge 2(n-1)\qquad(1)$ Now number the rows $1,2,...,n$. For $i=0,1$ or $2$, the rows $\equiv i \mod 3$ contain no more than $\frac{1}{3}|T|$ of the marked cells. Then divide the board into $3\times n$ subgrids with rows $\equiv i$ as the middle row. (Note, if $3\not | n$ then at the edges of the board we have some left over rows, so leave them out). Using (1) and summing over all $3\times n$ subgrids we get that $\frac{1}{3}|T| + 2|T| \ge 2(n-1)\frac{n}{3} - O(n)$ Therefore $|T| \ge \frac{2}{7} n^2 - O(n)$ as desired $\square$ Upper bound Let $T = \{(i,j) \, : \, 2i+j\equiv 1,4 \mod 7\}$. It is easy to see that any $k\times k$ grid has a marked point on it's boundary, and $|T| = \frac{2}{7}n^2 + O(n)$ Using these two estimates we find $\lim_{n\to \infty} \frac{l(n)}{n^2} \to \frac{2}{7}$ as desired $\qquad\square$