8. The park is a $10 \times 10$ grid of cells. A lamp can be placed in any cell (but no more than one lamp per cell).

a) The park is called illuminated if, no matter which cell a visitor is in, there is a $3 \times 3$ square of 9 cells that contains both the visitor and at least one lamp. What is the minimum number of lamps in an illuminated park?

b) The park is called reliably illuminated if it remains illuminated even after the failure of any one lamp. What is the minimum number of lamps in a reliably illuminated park?
Solution. a) 4. Divide the park into 4 quarters (squares $5 \times 5$), then there must be at least one lamp in each quarter (to illuminate, for example, the corner cells). By placing one lamp in the center of each quarter, we get an example.

b) 10.

Estimate. In each corner square $3 \times 3$ there must be at least two lamps (to illuminate the corner cell). Temporarily leave only these 8 lamps. Each of them illuminates only within its own quarter, and if the lamp in the center of the quarter breaks (or if it is absent), then a five-cell strip inside this quarter, adjacent to another quarter, will definitely not be illuminated. Note that the union of two such strips for opposite quarters cannot be illuminated by one lamp in any case, so at least two more lamps are needed.

Example:

![](https://cdn.mathpix.com/cropped/2024_05_06_eefd0f96dcd1008e56cag-3.jpg?height=543&width=591&top_left_y=1145&top_left_x=401)

Criteria. In part a) 1 point is given for the estimate and 1 point for the example. In part b) 3 points are given for the estimate (1 point if it is proven that 8 lamps are insufficient), and 2 points for the example.

![](https://cdn.mathpix.com/cropped/2024_05_06_eefd0f96dcd1008e56cag-4.jpg?height=277&width=294&top_left_y=113&top_left_x=161)

International Mathematical Olympiad

«Formula of Unity» / «The Third Millennium»

Year 2022/2023. Qualifying round

## Problems for grade R9

Each task is assessed at 7 points. Some problems have their own criteria (printed in gray).