# k-NN Point with All Four Predictions

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

*Task 3 of the school stage of the All-Russian School Olympiad (VsOSh) 2025/26 in artificial intelligence (region group III), grades 9–11. The official answer and solution are in a separate file.*

Points are given on the coordinate plane; each of them belongs to one of four classes numbered 0, 1, 2 or 3. The class of a new point is to be predicted by the $k$ nearest neighbours rule:

- for the chosen number $k$, take the $k$ training points closest to the point $q$;
- among the chosen $k$ points, count which class number occurs most often, and output that number;
- if several classes occurred equally often, choose the one among them for which the sum of the distances from $q$ to all points of this class (among the chosen $k$) is smaller, and if these sums are also equal, the class with the smaller number.

The training points are given:<br>
Class 0: red.<br>
Class 1: blue.<br>
Class 2: green.<br>
Class 3: yellow.<br>
Denote the total number of training points by $N$ (here $N$=18). Consider all integer points $q$ inside the smallest rectangle with sides parallel to the coordinate axes that contains all the given points. For each such point $q$, we write out the predictions of the $k$ nearest neighbours rule for $k = 1, 2, ..., N$.

*[Figure: see the [original statement](https://siriusolymp.ru/2025/ai).]*

*Translator's transcription of the figure (a scatter plot with $x$ from 0 to 10 and $y$ from −2 to 5):*

| Class | Marker in the figure | Points |
|---|---|---|
| 0 | red circle | $(8, 2)$, $(8, 3)$, $(9, 2)$ |
| 1 | blue square | $(2, 3)$, $(3, 4)$, $(4, 3)$, $(5, 3)$ |
| 2 | green triangle | $(5, 0)$, $(6, 0)$, $(7, 0)$, $(7, -1)$, $(8, -1)$ |
| 3 | orange diamond | $(1, 2)$, $(4, 2)$, $(2, 1)$, $(4, 1)$, $(6, 1)$, $(2, 0)$ |

Determine the coordinates of the unique integer point $q$ inside this rectangle for which, as $k$ runs through $1, 2, ..., 18$, the predictions contain each of the four classes 0, 1, 2, 3 at least once.

**Scoring criterion:** exact match of the answer — 12 points

**Maximum score for the task — 12**