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 parallel to the coordinate axes exists? Justify your answer.

![](https://cdn.mathpix.com/cropped/2024_06_07_f155edc146c61fd862beg-03.jpg?height=434&width=420&top_left_y=1619&top_left_x=1435)

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

## Problems for 3rd Year
II/4.

 1. method We must color at least four points. In the grid, we can inscribe four disjoint squares as shown in the first figure. Since each must have at least one red vertex, we need at least 4 red points.

We will show that this is also sufficient. Color the points as shown in the second figure. In the grid, we have one single $3 \times 3$ square, which clearly has two red vertices. In addition, we have four $2 \times 2$ squares, each with exactly one red vertex.

There remain 9 $1 \times 1$ squares. Four of them are already drawn in the first figure, and each clearly has at least one red vertex. The remaining 5 are drawn in the third figure, and each has at least one red vertex.
![](https://cdn.mathpix.com/cropped/2024_06_07_f155edc146c61fd862beg-09.jpg?height=266&width=1174&top_left_y=1068&top_left_x=452)

Proof that we need at least 4 red points ...................................... 4 points
Correct configuration of 4 red points written down ................................... 2 points
Proof that this configuration works (writing "the configuration works" does NOT suffice) ... 1 point

Note: The second 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.

 2. method First, we assign a potential to each point, which is the number of squares that have one of their vertices at that point. The twelve outer points have a potential of 3, and the four inner points have a potential of 5:

| 3 | 3 | 3 | 3 |
| :--- | :--- | :--- | :--- |
| 3 | 5 | 5 | 3 |
| 3 | 5 | 5 | 3 |
| 3 | 3 | 3 | 3 |

To show that we need to color at least 4 points, we can use the potentials as follows. By coloring three points (or fewer), we can exclude at most

(a) $3+3+3=9$

(b) $3+3+5=11$

(c) $3+5+5=13$

(d) $5+5+5=15$

squares. There are a total of $1+4+9=14$ squares, so we can immediately rule out options (a), (b), and (c). Option (d) is also invalid, as coloring three inner points leaves us with the largest square and one of the smallest squares:

![](https://cdn.mathpix.com/cropped/2024_06_07_f155edc146c61fd862beg-10.jpg?height=257&width=257&top_left_y=514&top_left_x=908)

Therefore, we must color at least 4 points. We conclude the proof as in the first method.

Introduction of potential .....................................................................................................

Justification that coloring three (or fewer) points is insufficient ...................... 3 points

Correct configuration of 4 red points written down .........................................................

Proof that this configuration works (writing "the configuration works" does NOT suffice) . . 1 point

Note: The second 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.