A square is divided into 16 equal squares, obtaining the set of 25 different vertices. What is the least number of vertices one must remove from this set, so that no 4 points of the remaining set are the vertices of any square with sides parallel to the sides of the initial square?

Remark. The proposed solution to this problem claimed that it is enough to remove 7 vertices but the example to demonstrate this appeared to be incorrect. Below we show that removing 6 vertices is not sufficient but removing 8 vertices is. It seems that removing 7 vertices is not sufficient but we currently know no potential way to prove this, apart from a tedious case study.
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.

12345

![](https://cdn.mathpix.com/cropped/2024_04_17_38aae83e469137ba6b44g-4.jpg?height=168&width=194&top_left_y=864&top_left_x=588)

$\mathrm{a}$

![](https://cdn.mathpix.com/cropped/2024_04_17_38aae83e469137ba6b44g-4.jpg?height=157&width=143&top_left_y=864&top_left_x=794)

$\mathrm{b}$

![](https://cdn.mathpix.com/cropped/2024_04_17_38aae83e469137ba6b44g-4.jpg?height=154&width=148&top_left_y=868&top_left_x=937)

c

![](https://cdn.mathpix.com/cropped/2024_04_17_38aae83e469137ba6b44g-4.jpg?height=154&width=148&top_left_y=868&top_left_x=1091)

d

![](https://cdn.mathpix.com/cropped/2024_04_17_38aae83e469137ba6b44g-4.jpg?height=154&width=146&top_left_y=868&top_left_x=1246)

e

![](https://cdn.mathpix.com/cropped/2024_04_17_38aae83e469137ba6b44g-4.jpg?height=154&width=149&top_left_y=868&top_left_x=1393)

f

Figure 3