# Final Stage 2025–2026, Tour 1: Full Paper

*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

---

## A. The Line Rotates Again

Consider a linear classifier on the plane $\mathbb{R}^2$ defined by the line $x + Ay = 0$. A point $(x, y)$ belongs to the first class if $x + Ay > 0$. Otherwise, if $x + Ay \leq 0$, the point belongs to the second class.

Give an example of **integers** $A$, $b$ and $c$ such that, for the trinomial $P(x) = x^2 + bx + c$, the point $(2, P(2))$ belongs to the first class, while the points $(1, P(1))$ and $(3, P(3))$ belong to the second class.

---

## B. Random Generator

A random number generator works as follows. If it is given a natural number $m \geq 6$, it outputs 10 natural numbers one after another. Each number is chosen by it independently and with equal probability from the set $\{1, 2, \ldots, m\}$.

Because of a system error, the generator's result is displayed on the screen as follows: the numbers $1, 2, 3, 4, 5$ are displayed unchanged, and in place of any other number the number $6$ is displayed.

For which natural number $m \geq 6$ is the probability of getting the sequence of numbers

$$6,\ 2,\ 6,\ 6,\ 1,\ 6,\ 4,\ 6,\ 3,\ 5$$

on the screen the greatest?

---

## C. Gradient Descent on Paper

Consider the function $f(x, y) = x^{20} + y^{26}$. Below is an algorithm that, given a starting point $(a, b)$, constructs a sequence of points $(X_i, Y_i)$, $i = 0, 1, 2, \ldots$

In the code below, `decrease_lr = False` for part (a), and `decrease_lr = True` for part (b).

```text
X_0, Y_0 ← a, b
dx, dy ← 0, 1
lr ← 1
for i = 1, 2, 3, ... do
    dx, dy ← dy, -dx
    if decrease_lr and i · lr ⩾ 2 then:
        lr ← lr / 2
    end if
    X_i, Y_i ← X_{i-1}, Y_{i-1}
    if f(X_i + dx · lr, Y_i + dy · lr) < f(X_i, Y_i) then
        X_i ← X_i + dx · lr
        Y_i ← Y_i + dy · lr
    end if
end for
```

Prove that, whatever the starting point, the following statements hold.

(a) There exists an index $N$ such that the distance from the point $(X_N, Y_N)$ to the origin does not exceed 1.

(b) There exists an index $N_0$ such that, for every index $N \geq N_0$, the distance from the point $(X_N, Y_N)$ to the origin does not exceed $\frac{1}{1000}$.

---

## D. Laser

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](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/final/ai/tasks-ai-9-11-tur1-final-25-26.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.]*

---

## E. New Sample

A model predicts a real number from a real number $x$ by the method of *linear regression*, that is, by the formula $f(x) = ax + b$, where $a, b \in \mathbb{R}$ are the parameters of the model $f$.

A *training sample* $(x_1, y_1), (x_2, y_2), \ldots (x_n, y_n)$ is given, where $x_1, \ldots, x_n, y_1, \ldots y_n \in \mathbb{R}$. The model $f$ is trained on these data: the parameters $a$ and $b$ are chosen by the *least-squares method*, that is, so that the value of the expression

$$\sum_{i=1}^{n} (y_i - f(x_i))^2$$

is minimal.

We define the *coefficient of determination* $R_0^2$, computed on this sample, as follows:

$$R_0^2 = 1 - \frac{\sum\limits_{i=1}^{n} (y_i - f(x_i))^2}{\sum\limits_{i=1}^{n} (y_i - \bar{y})^2}, \qquad \text{where} \quad \bar{y} = \frac{1}{n} \sum_{i=1}^{n} y_i.$$

We construct a new sample by adding the $n$ objects $(x_i, f(x_i))$, $i = 1, 2, \ldots, n$, to the original one. Let a model $g(x) = cx + d$ be trained on the resulting sample of $2n$ objects, also by the least-squares method. Denote by $R_1^2$ the coefficient of determination for the model $g$, computed on the sample of all $2n$ objects.

It is assumed that the parameters of both models could be determined by the least-squares method uniquely.

Express $R_1^2$ in terms of $R_0^2$.

---

## F. A Fictional Situation

Artur and Tanya are preparing computing resources for the practical tour for the 1000 participants of the final of the All-Russian School Olympiad in AI. Initially, they wanted to deploy the whole infrastructure in the cloud and hand out graphics cards (GPUs) from a common pool, but, to rule out network latency, it was decided to assemble a personal cluster of 8 devices for each participant.

The warehouse of the olympiad's partners holds 8000 devices of each of three types.

- Type 1 (green): CUDA, fast but hot.
- Type 2 (red): support open standards and are suitable for training large language models (LLMs), but require complicated driver set-up.
- Type 3 (yellow): experimental accelerators (TPUs).

Under the terms of delivery, devices of type 1 can be obtained only in batches of 7; there must be at least 2026 devices of each type; exactly 8000 devices in total must be taken from the warehouse. If, in accordance with these conditions, $y_1$ devices of the first type, $y_2$ of the second and $y_3$ of the third can be brought from the warehouse, we call the triple of integers $(y_1, y_2, y_3)$ *admissible*, that is:

$$y_1 + y_2 + y_3 = 8000, \qquad y_t \geq 2026 \ (t = 1, 2, 3), \qquad y_1 \,\vdots\, 7.$$

*(Translator's note: $y_1 \,\vdots\, 7$ is the Russian notation for "$y_1$ is divisible by 7".)*

Each participant has a personal code $i = 1, 2, \ldots, 1000$. The devices delivered from the warehouse are distributed among the participants. Let participant $i$ receive a personal cluster $S_i = (x_{i,1}, x_{i,2}, x_{i,3})$, in which $x_{i,1}, x_{i,2}, x_{i,3}$ are the numbers of devices of the first, second and third type respectively. The numbers $x_{i,1}, x_{i,2}, x_{i,3}$ are non-negative integers, and $x_{i,1} + x_{i,2} + x_{i,3} = 8$.

It turned out that some participants prefer the "greens", some are fans of open standards and choose the "reds", and some love the unusual "yellows". For each participant, device *preferences* $u_{i,1}, u_{i,2}, u_{i,3}$ are given; they are listed in the input file `gpu.csv`.

The file contains a header and 1000 rows with 3 columns of data: the $i$-th row contains three integers $u_{i,1}, u_{i,2}, u_{i,3}$ (in exactly this order), corresponding to the preferences of participant $i$.

The utility of a cluster $S = (x_1, x_2, x_3)$ for participant $i$ is given by the formula

$$V_i(S) = u_{i,1}x_1 + u_{i,2}x_2 + u_{i,3}x_3.$$

A distribution of devices is called *fair* if the inequality $V_i(S_i) \geq V_i(S_j)$ holds for any two participants $i, j$.

(a) Give an example of an admissible triple of values $(y_1, y_2, y_3)$ for which no fair distribution exists, and prove this.

(b) Does there exist an admissible triple $(y_1, y_2, y_3)$ for which a fair distribution exists?