# Final Stage 2025–2026, Tour 1: Solutions and Marking Criteria

*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.

### Solution

One example: $A = -4$, $b = -4$, $c = 4$, that is, $P(x) = (x - 2)^2 = x^2 - 4x + 4$. Let $L(x, y) = x - 4y$. Then

$$\begin{aligned}
L(1, P(1)) &= L(1, 1) = -3 \leq 0 \implies \text{the point } (1, P(1)) \text{ belongs to the second class;}\\
L(2, P(2)) &= L(2, 0) = 2 > 0 \implies \text{the point } (2, P(2)) \text{ belongs to the first class;}\\
L(3, P(3)) &= L(3, 1) = -1 \leq 0 \implies \text{the point } (3, P(3)) \text{ belongs to the second class.}
\end{aligned}$$

---

## 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?

### Solution

**Answer:** $m = 10$.

The probability that the number $k \in \{1, 2, 3, 4, 5\}$ appears at a given position of the sequence is

$$\mathbb{P}(k) = \frac{1}{m}.$$

Since all the other numbers are replaced by 6, the same probability for the number 6 is

$$\mathbb{P}(6) = \frac{m - 5}{m}.$$

In the sequence under study, the value 6 occurs 5 times, and the numbers $1, \ldots, 5$ occur another 5 times. Therefore, the probability of obtaining this sequence equals

$$\left(\frac{1}{m}\right)^5 \left(\frac{m - 5}{m}\right)^5 = \left(\frac{m - 5}{m^2}\right)^5.$$

The maximum value of this probability is attained when the quantity

$$\frac{m - 5}{m^2} = \frac{1}{m} - \frac{5}{m^2}$$

takes its largest possible value.

Let $x = \frac{1}{m}$. Since the maximum of the quadratic function $f(x) = x - 5x^2$ is attained at $x = \frac{1}{10}$, the required value is $m = 10$.

---

## 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}$.

### Solution

Let us study a single step of the algorithm. An *attempt* is made to change the value of one of the coordinates by some amount $lr$. This change happens if and only if the absolute value of the corresponding coordinate decreases, since

$$f(x + lr, y) < f(x, y) \iff |x + lr| < |x|,$$

$$f(x, y + lr) < f(x, y) \iff |y + lr| < |y|.$$

#### Part (a)

Along the $x$ coordinate the algorithm makes the change attempts $+1, -1, +1, -1, \ldots$; along the $y$ coordinate, conversely, $-1, +1, -1, +1, \ldots$.

Consider two consecutive attempts to change the $x$ coordinate.

- If $|x| > \frac{1}{2}$, then exactly one of the two attempts leads to a change of the coordinate, and $|x|$ decreases by exactly 1.
- If $|x| \leq \frac{1}{2}$, then neither attempt leads to a change of the coordinate.

Thus, after a finite number of such pairs of algorithm steps, the inequality $|x| \leq \frac{1}{2}$ will hold, since $|x|$ cannot decrease by 1 infinitely many times.

The same is true for the $y$ coordinate; hence, for some index $N$ the inequalities

$$|X_N| \leq \frac{1}{2}, \qquad |Y_N| \leq \frac{1}{2}$$

will hold.

Then the distance to the origin at that moment will also be less than 1:

$$X_N^2 + Y_N^2 \leq \frac{1}{4} + \frac{1}{4} = \frac{1}{2} < 1.$$

By what was said above, this inequality will also hold for every index $M \geq N$; we will need this observation to solve the other part.

#### Part (b)

Let us divide the steps of the algorithm into blocks of consecutive steps with the same value of $lr$. Consider the $m$-th block, consisting of the steps with indices $i = 2^m + 1, \ldots, 2^{m+1}$, where $lr = \frac{1}{2^m}$. From now on we study the blocks with $m \geq 3$.

Then, as in part a), within each block every second attempt to change the $x$ coordinate decreases the value of $|x|$ as long as the inequality $|x| > \frac{lr}{2} = \frac{1}{2^{m+1}}$ holds.

Hence, for the $m$-th block of steps at least one of the following statements holds.

1. After all steps of the $m$-th block have been performed, $|x| \leq \dfrac{lr}{2}$.
2. As a result of every fourth step of the algorithm (that is, of every second attempt to change the $x$ coordinate), the quantity $|x|$ decreased by $lr$. Thus, over this block of steps it decreased in total by $2^{m-2} \cdot lr = \frac{1}{4}$.

Note that case 2 could occur only for a finite number of blocks, since $|x|$ cannot decrease by $\frac{1}{4}$ infinitely many times.

Consequently, there exists a number $M_x$ such that, for the blocks with indices greater than $M_x$, the first statement holds.

Altogether, for $N > N_x = \max(2^{M_x+1}, 10)$ the inequalities

$$|X_N| \leq \frac{1}{2^{N_x+1}} \leq \frac{1}{2^{11}} < \frac{1}{2000}$$

will hold.

Similarly, for the $y$ coordinate there also exists an index $N_y$ such that, for $N > N_y$, the inequality $|Y_N| < \dfrac{1}{2000}$ holds.

Then, for $N > \max(N_x, N_y)$, the inequalities $|X_N| < \dfrac{1}{2000}$ and $|Y_N| < \dfrac{1}{2000}$ hold. Hence,

$$\sqrt{|X_N|^2 + |Y_N|^2} \leq \sqrt{|X_N|^2 + 2 \cdot |X_N||Y_N| + |Y|^2} = |X_N| + |Y_N| < \frac{1}{2000} + \frac{1}{2000} = \frac{1}{1000}.$$

Thus, the index $N_0 = \max(N_x, N_y)$ satisfies the conditions of the problem.

**Remark.** It follows from the solution above that the sequence of points $(X_i, Y_i)$ converges to the minimum point of the function $f(x, y)$, the origin.

---

## 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.]*

### 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.

---

## 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$.

### Solution

**Answer:** $R_1^2 = \dfrac{2R_0^2}{1 + R_0^2}$.

Let $\widehat{y}_i = f(x_i)$ (the prediction); $SSE_0 = \sum\limits_{i=1}^{n} (y_i - \widehat{y}_i)^2$ (the sum of squared errors), $SST_0 = \sum\limits_{i=1}^{n} (y_i - \bar{y})^2$ (the total sum of squares). Then $R_0^2 = 1 - \dfrac{SSE_0}{SST_0}$.

Similarly, we define the quantities $SSE_1$ and $SST_1$ for the second model.

**Lemma 1.** *The model trained on the combined sample coincides with the original one, and therefore $SSE_1 = SSE_0$.*

*Proof.* For the model $f$, the errors $(\widehat{y}_i - f(x_i))^2$ at the added points $(x_i, \widehat{y}_i)$ are equal to zero, and for the original points the sum of squared errors is the smallest possible. Hence, the minimum on the combined sample is attained at the same parameter values (and so the models coincide). $\square$

**Lemma 2.** *The following equalities hold:*

$$\sum_{i=1}^{n} (y_i - \widehat{y}_i) = 0 \quad \text{and} \quad \sum_{i=1}^{n} x_i (y_i - \widehat{y}_i) = 0.$$

*Proof.* The point $(a, b)$ is chosen by the least-squares method, that is, it is the point at which the function

$$F(u, v) = \sum_{i=1}^{n} (y_i - u x_i - v)^2$$

takes its smallest value. Hence, if we fix $u = a$, the resulting quadratic function of the variable $v$ attains its smallest value at the point $b$. This means that the $v$-coordinate of the vertex of the corresponding parabola equals $b$, that is,

$$-b = \frac{1}{n} \left( \sum_{i=1}^{n} (a x_i - y_i) \right) \implies 0 = \sum_{i=1}^{n} (a x_i + b) - \sum_{i=1}^{n} y_i = \sum_{i=1}^{n} (\widehat{y}_i - y_i).$$

Arguing similarly for $v = b$, we obtain the second stated relation:

$$-a \cdot \sum_{i=1}^{n} x_i^2 = \sum_{i=1}^{n} (b - y_i) x_i \implies 0 = \sum_{i=1}^{n} x_i (a x_i + b - y_i) = x_i (\widehat{y}_i - y_i).$$

$\square$

**Lemma 3.** *The equality $SST_1 = 2SST_0 - SSE_0$ holds.*

*Proof.* By Lemma 2, the equality $\dfrac{1}{n} \sum\limits_{i=1}^{n} \widehat{y}_i = \bar{y}$ holds. Hence,

$$SST_1 = \sum_{i=1}^{n} (y_i - \bar{y})^2 + \sum_{i=1}^{n} (\widehat{y}_i - \bar{y})^2 = SST_0 + \sum_{i=1}^{n} (\widehat{y}_i - \bar{y})^2.$$

Moreover, $y_i - \bar{y} = (y_i - \widehat{y}_i) + (\widehat{y}_i - \bar{y})$. Let us square all such equalities and then add them up. We obtain

$$SST_0 = \sum_{i=1}^{n} (y_i - \widehat{y}_i)^2 + \sum_{i=1}^{n} (\widehat{y}_i - \bar{y})^2 + 2 \sum_{i=1}^{n} (y_i - \widehat{y}_i)(\widehat{y}_i - \bar{y}).$$

The last term is zero. Indeed, let us use Lemma 2 as follows:

$$\sum_{i=1}^{n} (y_i - \widehat{y}_i)(\widehat{y}_i - \bar{y}) = \sum_{i=1}^{n} (y_i - \widehat{y}_i)\widehat{y}_i = a \sum_{i=1}^{n} x_i (y_i - \widehat{y}_i) + b \sum_{i=1}^{n} (y_i - \widehat{y}_i) = 0.$$

Then $SST_0 = SSE_0 + \sum\limits_{i=1}^{n} (\widehat{y}_i - \bar{y})^2$, which gives the required equality. $\square$

Putting together the results of Lemmas 1–3, we have:

$$R_1^2 = 1 - \frac{SSE_1}{SST_1} = 1 - \frac{SSE_0}{2SST_0 - SSE_0} = \frac{2(SST_0 - SSE_0)}{2SST_0 - SSE_0}.$$

Dividing the numerator and the denominator by $SST_0$, we obtain the stated answer:

$$R_1^2 = \frac{2\left(1 - \frac{SSE_0}{SST_0}\right)}{2 - \frac{SSE_0}{SST_0}} = \frac{2R_0^2}{1 + R_0^2}.$$

**Comment.** Lemma 2 can be proved differently, using the fact that the partial derivatives of the function $F(u, v)$ at the point $(a, b)$ are equal to zero.

---

## 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?

### Solution

We will call the quantities $u_{i,j}$ the *utilities* of devices of type $j$ for participant $i$.

**Lemma 1.** *If the utility values of an arbitrary participant $i$ are multiplied by the same positive number, any fair distribution remains fair, and any unfair one remains unfair.*

*Proof.* We multiply both sides of the inequalities in which the utility $V_i$ appears by the same positive constant; therefore, the system of new inequalities holds if and only if the system of the original ones does. $\square$

**Observation.** According to the data in the file `gpu.csv`, the students split into two groups.

- group $A$: 511 students whose utility vectors are proportional to

  $$u^A = (2053, 2063, 2070);$$

- group $B$: 489 students whose utility vectors are proportional to

  $$u^B = (2081, 2027, 2003).$$

By Lemma 1, we may assume that all participants of group $A$ have the utility vector $u^A$, and all participants of group $B$ have the utility vector $u^B$.

**Lemma 2.** *In any fair distribution, all students of group $B$ receive the same set of devices.*

*Proof.* Take two participants of group $B$. Let the first receive $b_i$ devices of type $i$, and the second $b'_i$ devices of type $i$. Since the preferences of these participants coincide, the utilities of the clusters $(b_1, b_2, b_3)$ and $(b'_1, b'_2, b'_3)$ for them also coincide, and they are equal to each other. That is,

$$2081 b_1 + 2027 b_2 + 2003 b_3 = 2087 b'_1 + 2027 b'_2 + 2003 b'_3.$$

Since each cluster contains 8 devices, subtracting $2003 \cdot 8$ from both sides, we get

$$\begin{gathered}
(2081 - 2003) b_1 + (2027 - 2003) b_2 = (2081 - 2003) b'_1 + (2027 - 2003) b'_2 \Rightarrow \\
78(b_1 - b'_1) + 24(b_1 - b'_2) = 0 \Rightarrow 13(b_1 - b'_1) + 4(b_2 - b'_2) = 0
\end{gathered}$$

Hence, the number $b_2 - b'_2$ is a multiple of 13. However, since $0 \leq b_2, b'_2 \leq 8$, this is possible only if $b_2 = b'_2$, and then also $b_1 = b'_1$, $b_3 = b'_3$, which completes the proof of the lemma. $\square$

**Lemma 3.** *In any fair distribution, all students of group $A$ receive the same set of devices.*

*Proof.* The argument is, on the whole, similar to that of the previous lemma. Again, assuming the contrary, we have two clusters $(a_1, a_2, a_3)$ and $(a'_1, a'_2, a'_3)$ of equal utility for a participant of group $A$. Now, since $2053 - 2070 = -17$ and $2063 - 2070 = -7$, we have: $-17(a_1 - a'_1) - 7(a_2 - a'_2) = 0$. Consequently, $a_2 - a'_2$ is divisible by 17, so $a_2 = a'_2$, and then also $a_1 = a'_1$, $a_3 = a'_3$; the lemma is proved. $\square$

Altogether, all 511 students of group $A$ receive the same cluster $a = (a_1, a_2, a_3)$, and all 489 students of group $B$ receive the same cluster $b = (b_1, b_2, b_3)$.

Let us count the number of devices of each type:

$$y_t = 511 a_t + 489 b_t \qquad (t = 1, 2, 3).$$

#### Part (a)

Consider the triple $(y_1, y_2, y_3) = (2100, 2100, 3800)$. It is easy to see that it is admissible: 2100 is divisible by 7, all $y_i$ are at least 2026, and $2100 + 2100 + 3800 = 8000$. Let us prove that no fair distribution exists for this triple.

Suppose the contrary. By what was said above, for some clusters $a = (a_1, a_2, a_3)$ and $b = (b_1, b_2, b_3)$ the equality $2100 = y_1 = 511 a_1 + 489 b_1$ holds. But the numbers of the form $2100 - 511n$ are not divisible by 489 for $n = 0, 1, 2, 3$, and are negative for $n \geq 4$; a contradiction.

#### Part (b)

**Answer:** such a triple exists.

Consider the following distribution: each student of group $A$ gets the cluster (0,4,4), and each student of group $B$ gets the cluster (7,1,0).

Let us compute the number of devices of each type:

$$y_1 = 511 \cdot 0 + 489 \cdot 7 = 3423, \qquad y_2 = 511 \cdot 4 + 489 \cdot 1 = 2044 + 489 = 2533, \qquad y_3 = 511 \cdot 4 + 489 \cdot 0 = 2044.$$

Note that $y_1$ is divisible by 7, and the number of devices of each type is at least 2026. Thus, this distribution corresponds to the admissible triple

$$(y_1, y_2, y_3) = (3423, 2533, 2044).$$

Let us check that the distribution obtained is fair. For any student $i$ from group $A$:

$$\begin{aligned}
V_i(a) &= 2053 \cdot 0 + 2063 \cdot 4 + 2070 \cdot 4 = 8252 + 8280 = 16532,\\
V_i(b) &= 2053 \cdot 7 + 2063 \cdot 1 + 2070 \cdot 0 = 14371 + 2063 = 16434.
\end{aligned}$$

Hence, $V_i(a) > V_i(b)$. Let us do the same computation for a student participant $j$ from group $B$:

$$\begin{aligned}
V_j(a) &= 2081 \cdot 0 + 2027 \cdot 4 + 2003 \cdot 4 = 8108 + 8012 = 16120,\\
V_j(b) &= 2081 \cdot 7 + 2027 \cdot 1 + 2003 \cdot 0 = 14567 + 2027 = 16594.
\end{aligned}$$

Consequently, $V_j(b) > V_j(a)$. Altogether, every participant of group $B$ prefers their own cluster to the cluster of group $A$, and vice versa. Since the participants within each group receive identical clusters, the distribution is fair. Thus, the triple

$$(y_1, y_2, y_3) = (3423, 2533, 2044)$$

works.

**Remark.** One can prove that the triple given is the only one that satisfies the conditions of part (b). Therefore, any other admissible triple will do as an example for part (a).

---

## Marking criteria for the first tour

All-Russian School Olympiad in Informatics 2025–2026, Final Stage<br>
“Artificial Intelligence” profile. Marking criteria for the first tour.

### A. The Line Rotates Again

A. Correct answer without verification: 45 points.

### B. Random Generator

A. $\mathbb{P}(6) = (m - 5)/m$ is found: 5 points.

B. The probability of the sequence from the statement is found for a fixed $m$: 15 points.

C. It is stated that the probability from the previous criterion increases for integer $m$ from 6 to 10 and decreases after that: 15 points.

D. The probability is computed with an error of a constant factor (or other inaccuracies that do not affect the course of the solution): at least 5 points are deducted.

M. It is proved that the number 10 is an extremum. It is used, but not proved, that it is precisely a maximum: at least 5 points are deducted.

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

### C. Gradient Descent on Paper

General part.

C1 (5 points) The alternation of the descent directions with period 4 is stated.

C2 (5 points) The decrease of $|X|$ and $|Y|$ is established.

Part (a).

A. A correct proof of part (a): 20 points.

MA. The stopping region is given incorrectly, or the existence of such a region is used without proof: 10 points are deducted.

Part (b).

B. A correct proof of part (b): 20 points.

B1. The block structure is introduced, with the relation between the block sizes and the common value of $lr$ indicated: 5 points.

B2. It is proved that the contribution of each block to the change of the parameters $|X|$ and $|Y|$ is at least some constant if all steps of this block led to a change of the corresponding coordinates.

MB. Errors in the presentation of the remaining part of the proof: at least 5 points are deducted.

- The progress items and penalties for the three listed parts of the problem are added up.

### D. Laser

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.

### E. New Sample

Well-known properties of linear regression are accepted without proof **provided they are stated correctly**.

A. Correct answer: 10 points.

B. It is proved that $f = g$: 10 points.

- If it is only stated that $f = g$, 5 points are awarded.
- If the proof relies on properties of linear regression, the property of the added data that allows one to conclude that the coefficients of the models are equal must be stated explicitly.
- If this is used and not even stated, no points are awarded under criterion $B$.
- No additional points are awarded for concluding that the numerators in the expressions for the coefficient of determination are equal.

C1. The relations between $y_i, x_i, f(x_i)$ are established (Lemma 2): 10 points.

C2. Expressions for $a$ and $b$ are obtained (the formula for the linear regression coefficients), with a proof that the means are equal: 10 points.

- **Both** relations must be established (in the form given in C1 or C2), and the equality of the means of the old and the new sample must be stated explicitly. For obtaining any one of the relations, 5 points are awarded for part $C$.

M. Lemma 3 (or an analogous equality) is used in the solution without proof: 15 points are deducted.

- No points are awarded for algebraic transformations that do not lead to a dependence of $R_1^2$ **only** on $R_0^2$.

### F. A Fictional Situation

A. Correct answer in part (a): 0 points.

B. Lemma 1 (on multiplying the utilities by a constant) together with the observation that the participants split into two groups: 10 points.

B1. The split of the agents into 2 groups by preferences is indicated: 5 points.

B2. Lemma 1 is only stated: 5 points.

C. Statement and proof of Lemmas 2 and 3 (on the equality of the clusters within each of the groups of participants): 15 points.

C1. Statement of Lemmas 2 and 3: 5 points.

D. Derivation of part (a) from Lemmas 2 and 3: 5 points.

E. Answer in part (b): 10 points.

F. Verification of the answer in part (b): 10 points.