A Fictional Situation

A Fictional Situation

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 F

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?