k Nearest Neighbours on Three Points

k Nearest Neighbours on Three Points

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 I), grades 9–11. The official answer and solution are in a separate file.

There are 18 points with integer coordinates on the plane. Each point has a class number: 0, 1, 2 or 3.

Class 0: red.
Class 1: blue.
Class 2: green.
Class 3: yellow.

Determine for which $k$ the $k$ nearest neighbours method correctly guesses the class of the three chosen points. The method works as follows: for a new point, we find the $k$ points from the list that are nearest to it. If several points are at the same distance, the one with the smaller class number is considered nearer. We count which class number occurs most often among these $k$ points; that number is the one chosen. If the frequencies are equal, the following rules are applied:

1. Among these classes, we choose the one whose sum of distances to the new point is smaller.
2. If there is a tie again, we take the class with the smaller number.

Let us single out three points: $(8; 2)$ of class 0, $(3; 4)$ of class 1 and $(5; 0)$ of class 2. To make the check fair, these three points are removed from the list in advance, and then the class of each of them is determined from the remaining 15 points.

[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; the three singled-out points are drawn in a paler shade):

Choose the number of neighbours for which the method correctly determines the class of all three singled-out points simultaneously:

[The answer options are not listed in the original file.]

Scoring criterion: (Number of correct choices − Number of incorrect choices) × 4, minimum 0 points

Maximum score for the task — 12