# k-NN Point with All Four Predictions: 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 III), grades 9–11. Answer and official solution.*

**Answer:** $q = (7, 4)$

**Solution.**

One can notice that if a point is far from the red or the blue cluster, it cannot be assigned the corresponding class for any $k$. For example, if the point is at the bottom left, then 4 orange points will be collected among the nearest neighbours first, and the 3 red ones will no longer be able to affect the answer. The same applies to the four blue points.

Hence, it makes sense to look only at the points between the red and the blue clusters. Let us prove that the point $(7, 4)$ fits.

Let us sort the neighbours of $q = (7, 4)$ (in ascending order of $r^2$; in case of equality, the smaller class number comes first):

| $k$ | point | class | $r^2$ |
|---:|:---:|:---:|---:|
| 1 | $(8, 3)$ | 0 | 2 |
| 2 | $(8, 2)$ | 0 | 5 |
| 3 | $(5, 3)$ | 1 | 5 |
| 4 | $(9, 2)$ | 0 | 8 |
| 5 | $(4, 3)$ | 1 | 10 |
| 6 | $(6, 1)$ | 3 | 10 |
| 7 | $(4, 2)$ | 3 | 13 |
| 8 | $(3, 4)$ | 1 | 16 |
| 9 | $(7, 0)$ | 2 | 16 |
| 10 | $(6, 0)$ | 2 | 17 |
| 11 | $(4, 1)$ | 3 | 18 |
| 12 | $(5, 0)$ | 2 | 20 |
| 13 | $(7, -1)$ | 2 | 25 |
| 14 | $(2, 3)$ | 1 | 26 |
| 15 | $(8, -1)$ | 2 | 26 |
| 16 | $(2, 1)$ | 3 | 34 |
| 17 | $(1, 2)$ | 3 | 40 |
| 18 | $(2, 0)$ | 3 | 41 |

**The model's answer as $k$ increases:**

| $k$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| class (answer) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 1 | 2 | 2 | 2 | 3 |

*Explanation of the ties.* For $k = 8$, classes 0 and 1 have three points each, but the sum of distances is smaller for class 0 — we take 0. For $k = 14$ there is a 1–2 tie; 1 wins by the smaller sum of distances. For $k = 17$ there is a 2–3 tie; 2 wins by the smaller sum of distances.

So, as $k$ runs through $1, 2, \ldots, 18$, all four classes $0, 1, 2, 3$ occur among the answers, which is what we need. (Checking the remaining integer points inside the rectangle shows that the only suitable point is $q = (7, 4)$.)

This task could also be solved by programming.

```python
from collections import Counter, defaultdict

P = {
    0: [(8, 2), (8, 3), (9, 2)],
    1: [(3, 4), (4, 3), (5, 3), (2, 3)],
    2: [(7, 0), (8, -1), (7, -1), (6, 0), (5, 0)],
    3: [(1, 2), (6, 1), (4, 2), (2, 0), (2, 1), (4, 1)],
}
S = [(x, y, c) for c in P for x, y in P[c]]
xs, ys = zip(*[(x, y) for x, y, _ in S])

def seq(X, Y):
    d = sorted(
        ((x - X) ** 2 + (y - Y) ** 2, c) for x, y, c in S
    )
    cnt = Counter()
    s = defaultdict(float)
    out = []
    for r2, c in d:
        cnt[c] += 1
        s[c] += r2**0.5
        m = max(cnt.values())
        C = [t for t in cnt if cnt[t] == m]
        out.append(
            min(C, key=lambda t: (s[t], t))
        )
    return out

ans = [
    (X, Y)
    for X in range(min(xs), max(xs) + 1)
    for Y in range(min(ys), max(ys) + 1)
    if len(set(seq(X, Y))) == 4
]
print(ans)
```