Vova has a square grid $72\times 72$. Unfortunately, $n$ cells are stained with coffee. Determine if Vova always can cut out a clean square $3\times 3$ without its central cell, if a) $n=699$; b) $n=750$.
Problem
Source: IV Caucasus Mathematic Olympiad
Tags: combinatorics
MellowMelon
09.04.2019 05:45
Call a $3 \times 3$ square without its center a ring. The possible rings we can cut out at first correspond to choosing the center cell among the $70 \times 70$ interior cells. Each stained square $S$ eliminates up to eight of these rings, which themselves corresponding to the ring whose center is $S$. If no clean ring can be cut out, then the rings corresponding to each stained square cover all $70 \times 70$ interior cells. So in reality, we are interested in the minimum number $N$ of rings we must place to cover all cells of a $70 \times 70$ grid, where rings can overlap each other and the edges of the grid.
For (a), we claim a clean ring always exists. It suffices to show $N \geq 700$. Take any covering, and go through its rings in some fixed order. For each ring, there are two cases:
1. Its central cell needs covering, and we haven't run into a ring covering its central cell. Pair it with some ring covering that central cell. These two rings together cover at most 14 different cells, so each ring contributes at most 7 cells. Delete both rings from our ordering.
2. Its central cell is either not in the grid or we already found a ring covering that cell. Then this ring covers at most 5 cells not covered by rings we've already dealt with. Delete this ring from our ordering.
In both cases, we find that each ring contributes at most 7 cells to the covering on average. We have $70^2 = 4900$ cells to cover, so at least 700 rings are needed in the whole covering.
For (b), we claim a clean ring does not always exist. It suffices to show $N \leq 750$. In fact we will show $N \leq \lfloor 72^2/7 \rfloor = 740$. There exists a way to form a nonoverlapping tesselation of an infinite square grid using only copies of the following polyomino:
[asy][asy]
size(50);
for (int i = 1; i <= 3; i += 1) {
draw((0,i)--(4,i));
draw((i,0)--(i,4));
}
draw((0,3)--(0,0)--(3,0));
draw((1,4)--(4,4)--(4,1));
dot((1.5, 1.5));
dot((2.5, 2.5));
[/asy][/asy]
In the tesselation, 1/7 of the squares will be dotted. So there exists a 72 by 72 subgrid $G$ of the tesselation containing at most $72^2/7$ dotted squares. Align our 70 by 70 grid with the interior squares of $G$, and place rings at the dotted squares of $G$. This will cover the entire 70 by 70 grid with at most $72^2/7$ rings.