4. A $7 \times 7$ table is divided into 49 squares. We place tiles of the shape

![](https://cdn.mathpix.com/cropped/2024_06_07_c45646d9586b6df064a6g-03.jpg?height=126&width=751&top_left_y=1522&top_left_x=698)

each covering two squares. What is the minimum number of tiles we need to place on the table so that each uncovered square has at least one adjacent square covered? (Squares are adjacent if they share a side.)

## 55th Mathematical Competition for High School Students in Slovenia, Nova Gorica, April 16, 2011

## Problems for 3rd Year

Solve the problems independently. You have 210 minutes to solve them.

![](https://cdn.mathpix.com/cropped/2024_06_07_c45646d9586b6df064a6g-04.jpg?height=160&width=334&top_left_y=363&top_left_x=1581)
The use of notes, literature, or a pocket calculator is not allowed.
II/4. We can place nine tiles on the table as shown in the first image. Each uncovered field has at least one adjacent field covered. Justify that we cannot do this with fewer than nine tiles. Consider the tile that lies on the table.
![](https://cdn.mathpix.com/cropped/2024_06_07_c45646d9586b6df064a6g-10.jpg?height=372&width=938&top_left_y=1730&top_left_x=911)
Let's mark the fields that are adjacent to the covered ones. In each row, there are at most three fields that are either covered or adjacent to a covered field, and these fields are consecutive. The same applies to columns and diagonals. Let's color nine fields as shown in the third image. If we could cover the table with at most eight tiles such that each field is either covered or adjacent to a covered field, one of these tiles would have to cover or be adjacent to two of the colored fields, which is not possible.

Example of a table with nine tiles that meet the conditions 2 points Proper coloring of 9 fields (as in the third image) 2 points Observation that one tile cannot simultaneously cover or be adjacent to two of the colored fields 1 point Justification that one tile cannot simultaneously cover or be adjacent to two of the colored fields 1 point

#### Abstract

If the competitor approaches the proof that eight tiles do not suffice but fails to prove it and does not achieve partial points according to the above criteria, they can receive a maximum of two points for this part of the solution, specifically for one of the following conclusions:

Justification that six tiles do not suffice

1 point

Justification that seven tiles do not suffice

2 points