# k Nearest Neighbours on Three Points: 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.*

*Task 3 of the school stage of the All-Russian School Olympiad (VsOSh) 2025/26 in artificial intelligence (region group I), grades 9–11. Answer and official solution.*

**Answer:** 1, 2, 5

**Solution.**

Before classification, each of the three singled-out points is excluded from the training set.

*Point $(8, 2)$, true class 0.* Nearest neighbours:

$$(8, 3)\ (0),\ (9, 2)\ (0) \text{ at } 1; \quad (7, 0)\ (2),\ (6, 1)\ (3) \text{ at } \sqrt{5}; \ \ldots$$

For $k = 1, 2$ the answer is 0. For $k = 3$ the third neighbour is taken with the smaller class number among the points at the equal distance $\sqrt{5}$, that is, class 2; the count is 0:2 versus 2:1 — class 0 wins. For $k = 4, 5$ class 0 keeps the majority.

*Point $(3, 4)$, true class 1.* Nearest:

$$(4, 3)\ (1),\ (2, 3)\ (1) \text{ at } \sqrt{2}; \quad (5, 3)\ (1),\ (4, 2)\ (3) \text{ at } \sqrt{5}; \ \ldots$$

For $k = 1, 2$ the answer is 1. For $k = 3$ the third point taken is $(5, 3)$ of class 1 (it has the smaller class number at the equal distance $\sqrt{5}$), so the answer is 1. For $k = 4$ the count is 1:3 versus 3:1 — again 1.

*Point $(5, 0)$, true class 2.* Order of distances:

$$(6, 0)\ (2) \text{ at } 1; \quad (6, 1)\ (3),\ (4, 1)\ (3) \text{ at } \sqrt{2}; \quad (7, 0)\ (2) \text{ at } 2; \quad (7, -1)\ (2),\ (4, 2)\ (3) \text{ at } \sqrt{5}; \ \ldots$$

- $k = 1$: class 2 — correct.
- $k = 2$: a tie between classes 2 and 3; we compare the sums of distances: class 2: 1, class 3: $\sqrt{2}$; we take 2 — correct.
- $k = 3$: two neighbours of class 3 and one of class 2 — an error.
- $k = 4$: a 2:2 tie; sums of distances: for class 2: $1 + 2 = 3$; for class 3: $\sqrt{2} + \sqrt{2} \approx 2.828$; class 3 is chosen — an error.
- $k = 5$: $(7, -1)$ of class 2 is added; the count is 3:2 in favour of class 2 — correct.
- $k \ge 6$: the point $(8, 2)$ has at least three green neighbours $(6, 0), (7, 0), (8, -1)$, which means it will certainly not be classified as red.

Thus, all three points are classified correctly at the same time exactly for $\boxed{k = 1,\ 2,\ 5}$.