# A Fictional Situation: 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 F

*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

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

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.