4. In the plane, there are 16 black points, as shown in the figure. What is the minimum number of these points that we need to color red so that no square with vertices in the remaining black points and sides of natural number lengths or $\sqrt{2}$ exists? Justify your answer.

![](https://cdn.mathpix.com/cropped/2024_06_07_f155edc146c61fd862beg-05.jpg?height=425&width=425&top_left_y=1798&top_left_x=1432)

Solve the problems independently. You have 210 minutes for solving. The use of notes, literature, or a pocket calculator is not allowed.

## 51st Mathematical Competition for High School Students in Slovenia

Maribor, April 21, 2007

## Solutions to the Problems
IV/4. We will prove that we need to color five points.
![](https://cdn.mathpix.com/cropped/2024_06_07_f155edc146c61fd862beg-15.jpg?height=264&width=742&top_left_y=1224&top_left_x=662)

Since at least one vertex in each of the 4 squares \(A, B, C, D\), marked in the first figure, must be red, we need at least 4 red points. Suppose this is already sufficient. A \(3 \times 3\) square has at least one red vertex. We can assume that this vertex is \((1,1)\). Therefore, the remaining vertices of square \(A\) are black. Let's consider square \(E\). Since the vertices common to \(A\) and \(E\) are black, one of the vertices common to \(B\) and \(E\) must be red. The remaining vertices in \(B\) are thus black. Similarly, we conclude for squares \(F\) and \(D\).

Square \(G\), shown in the third sketch, already has 3 black vertices, so vertex \((4,4)\) must be red.
![](https://cdn.mathpix.com/cropped/2024_06_07_f155edc146c61fd862beg-15.jpg?height=270&width=724&top_left_y=2006&top_left_x=674)

Squares \(H\) and \(K\) already have three black vertices, so the remaining ones must be red. This contradicts the assumption that there is only one red vertex in \(D\).

We have thus proven that at least 5 points must be colored red. As shown in the following figure, 5 red points are sufficient.

Justification that we need at least 4 red points ...................................................................

Sketch or construction showing that 5 red points are sufficient .......................................................

Complete treatment of all cases and conclusion that 4 red points are not enough .... 3 points

Note: For each omitted case or conclusion "the point is in the most squares, so it is best to color it," one point will be deducted. The last figure shows one of the possible ways to color the points red. The contestant can draw another configuration and adjust the proof to this configuration.