k-NN Point with All Four Predictions

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 [email protected].

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:
Class 0: red.
Class 1: blue.
Class 2: green.
Class 3: yellow.
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.]

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

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