# Laser: Official Solution

*English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email sota.ai.community@gmail.com.*

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

*The official solutions file repeats each statement before its solution; the statement is in the task statement file. The marking criteria below come from the “Marking criteria for the first tour” pages at the end of the same file.*

## Solution

**Answer:** $s = 3$.

Consider the kernel

$$K = \begin{pmatrix} 0 & 1 & 0 \\ -1 & 0 & -1 \\ 0 & 1 & 0 \end{pmatrix}.$$

Let us show that it works. Note that the trajectories of all beams split into cycles, because each sensor receives and emits exactly one beam (note that one cycle may be the union of the trajectories of several beams at once). Note that it suffices to check the condition for a single cyclic trajectory (by the linearity of convolution). We will think of such a trajectory as a set of diagonal segments between consecutive reflections, where each segment increases the value of every sensor lying on it by $1^\circ\mathrm{C}$. It is easy to see that the heat map of the trajectory equals the sum of the heat maps of these segments.

Hence, it suffices to check that convolving with the kernel $K$ any matrix in which the ones lie on a single diagonal line (and the other elements are zeros) gives the zero matrix. This follows from the fact that the sum of the elements of the matrix $K$ along any diagonal line is zero.

It remains to prove that smaller values of $s$ do not work. It suffices to prove this for $s = 2$. Suppose the contrary: there is a determining kernel

$$K = \begin{pmatrix} a & b \\ c & d \end{pmatrix}.$$

Consider a cyclic trajectory similar to the one shown in the second figure of the statement (passing through two opposite corners). It is easy to see that, by placing the 300 devices at the centres of the cells that it crosses, one can make **only** this trajectory appear (all beams from the devices must be directed "along" it).

Let it pass through the lower-left corner $(0, 0)$. Then, after convolution with the kernel $K$, we get $B[1][0] = 2a$ and $B[0][1] = 2d$. Hence $a = d = 0$. Arguing similarly for the trajectory passing through the other two corners, we get $b = c = 0$, a contradiction.

## Marking criteria

Part A (example). Part B (bound).

A1. The correct matrix $K$ is given: 10 points.

A2. It is shown that the matrix zeroes out diagonal lines: 5 points.

A3. Completion of the justification of why the matrix $K$ is a determining kernel: 10 points.

B1. A linear equation on the elements of the kernel is obtained: 5 points.

M. Errors in the construction of the "suitable beam" (it is considered only locally, fewer devices are placed than the statement requires, etc.): at least 5 points are deducted.

- All the listed progress items and penalties are added up.