Baltic Way 1993 · Problem 14

Solution:

The example in Figure 3a demonstrates that it suffices to remove 8 vertices to "destroy" all squares. Assume now that we have managed to do that by removing only 6 vertices. Denote the horizontal and vertical lines by $A, B, \ldots, E$ and $1,2, \ldots, 5$ respectively. Obviously, one of the removed vertices must be a vertex of the big square - let this be vertex $A 1$. Then, in order to "destroy" all the squares shown in Figure $3 \mathrm{~b}-\mathrm{e}$ we have to remove vertices $B 2, C 3, D 4, D 2$ and $B 4$. Thus we have removed 6 vertices without having any choice but a square shown in Figure $3 \mathrm{f}$ is still left intact.

$\mathrm{a}$ $\mathrm{b}$ c d e f Figure 3