Laser

Laser

English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email [email protected].

All-Russian School Olympiad in Informatics 2025–2026, Final Stage
“Artificial Intelligence” profile, Tour 1, Moscow, 23 March 2026
Task D

The floor of a rectangular chamber with mirrored walls has the shape of a $1000 \times 3000$ grid rectangle. Temperature sensors are placed at the grid nodes ($1001 \cdot 3001$ sensors in total). Initially, all sensors show a temperature of $0^\circ\mathrm{C}$.

At the centres of some cells there is one device each that emits laser beams. Each device emits a laser beam along a diagonal of the cell at whose centre it is located (that is, in one of the four possible directions, towards one of the nodes of that cell). The same device absorbs beams arriving from the opposite node. The device does not affect beams travelling in the other three directions.

In total, 300 devices are installed, each emitting one beam. Each beam is reflected specularly from the walls (on hitting a corner, the beam is reflected back in the opposite direction) until it is absorbed by one of the devices.

A laser beam, on "visiting" a temperature sensor, increases its reading by $1^\circ\mathrm{C}$. If the beam is reflected at the point where a sensor is located, it increases the reading of that sensor by $2^\circ\mathrm{C}$ at once. We call the heat map the matrix $A$ of size $1001 \times 3001$ whose elements are equal to the final readings of the corresponding temperature sensors.

To check that the sensor readings are correct, the values obtained are analysed as follows. A square matrix $K$ of size $s \times s$, called a kernel of size $s$, is chosen, and then the convolution of the matrix $A$ with the kernel $K$ is computed, that is, the matrix $B = A \star K$ of size $(1002 - s) \times (3002 - s)$, where

$$B[i][j] = \sum_{u=0}^{s-1} \sum_{v=0}^{s-1} A[i+u][j+v]\,K[u][v], \qquad 0 \leq i \leq 1001 - s, \quad 0 \leq j \leq 3001 - s.$$

We call a kernel $K$ determining if, for any heat map $A$, all elements of the matrix $B$ are equal to zero, while not all elements of the kernel $K$ are equal to 0. For what smallest value of $s$ does a determining kernel of size $s$ exist?

The figure below shows how a launched beam changes the temperature at the sensors until it is absorbed.

[Figure: see the original statement (page 2 of the PDF). Two panels, each titled "Chamber of 4×12 cells, T=24", with the legend "trajectory", "reflections", "device"; the axes are x (0 to 12) and y (0 to 4), and each node on the beam's path is labelled with its final reading. Left panel: the device at the centre of the cell (11.5, 0.5) emits its beam towards the node (11, 0). The beam travels (11, 0) → (7, 4) → (3, 0) → (0, 3) → (1, 4) → (5, 0) → (9, 4) → (12, 1) and then returns to the device, which absorbs it. The reflection nodes (11, 0), (7, 4), (3, 0), (0, 3), (1, 4), (5, 0), (9, 4), (12, 1) read 2; the nodes (4, 1) and (8, 3), where the path crosses itself, read 2; every other node on the path reads 1. Right panel: the device at the centre of the cell (11.5, 0.5) emits its beam towards the node (11, 1). The beam travels (11, 1) → (8, 4) → (4, 0) → (0, 4); the corner (0, 4) sends it back along the same path to (11, 1); it passes through the device's cell to the corner (12, 0), is reflected back and is absorbed by the device. The corners (0, 4) and (12, 0) read 2, the reflection nodes (8, 4) and (4, 0) read 4, and every other node on the path reads 2.]