1 A square grid of 16 dots (see the figure) contains the corners of nine $1 \times 1$ squares, four $2 \times 2$ squares, and one $3 \times 3$ square, for a total of 14 squares whose sides are parallel to the sides of the grid. What is the smallest possible number of dots you can remove so that, after removing those dots, each of the 14 squares is missing at least one corner?
Justify your answer by showing both that the number of dots you claim is sufficient and by explaining why no smaller number of dots will work.
Solution:
The answer is four dots.
Four is necessary, because the four corner $1 \times 1$ squares do not share any dots in common. Other arguments that four is necessary include using the $2 \times 2$ squares, or carefully counting the number of squares eliminated by each dot ( 5 in the center and 3 in the corner), and since one dot must be a corner dot, then at most $3+5+5$ squares can be removed by three dots.
Removing two opposite corners of the grid and two center dots along the other diagonal provides an example to show that four is sufficient.
See the figure for one of two such possible solutions.