Combinatorics Problem from Malaysia TST 2022

投稿日:2023/1/3最終更新日:2025/5/17

I hate combinatorics 😡

Berikut ini ada sebuah soal kombinatorika yang diberikan saat tahapan IMO Team Selection Test di Malaysia. Authornya adalah teman saya yang bernama Ivan Chan (Malaysia), anaknya imba sekali. Soalnya adalah sebagai berikut.

Problem Statement

Let $S$ be a set of $2023$ points in a plane, and it is known that the distances of any two different points in $S$ are all distinct. Ivan colors the points with $k$ colors such that for every point $P \in S$, the closest and the furthest point from $P$ in $S$ also have the same color as $P$.

What is the maximum possible value of $k$?

Solution

Consider a directed graph $G$, each vertex represents a point of $S$ and we connect two vertices $a \to b$ if $b$ is the closest point from $a$. Graph $G$ consists of several connected components, in which each component consists of at least two vertices, and every point in a component must be coloured with the same colour. Also, a connected component is a union of a cycle and disjoint paths. Note that no cycle with a length greater than two may occur, since if $p \to q \to r$ is a path, then
$d(q,r) < d(p,q)$
since $r$ is the closest point from $q$.

If a point $V$ with colour $C$ has its furthest point in a different connected component, there are at least four points with colour $C$. Otherwise, if its furthest point is in the same connected component, then it's possible that there can only be three points with colour $C$. Let's say the colour that only has three points as nice colour. We claim that there is only at most one nice colour.

For a nice colour, its points must be in the same connected component. Let's say the points and the edges $a \to b \leftrightarrow c$ (So $b$ is the closest point from $a$, $c$ is the closest point from $b$, and $b$ is the closest point from $c$). We must have $c$ as the furthest point from $a$, and $a$ as the furthest point from both $b$ and $c$. Let say we have another nice colour with connected component $a_1 \to b_1 \leftrightarrow c_1$. Then since $a$ is the furthest from $b$ and $b_1$ is the closest from $a_1$, we have:
$d(a,b) > d(a_1,b) > d(a_1,b_1),$
and similarly by symmetry we should have $d(a_1,b_1) > d(a,b)$. A contradiction.

Therefore, there are at most one nice colour. If $k$ denotes the number of the colours, we have:
$2023 \geq 4(k-1) + 3 \implies 506 \geq k.$

Komentar Ketika pertama kali membaca dan mengerjakan soal ini, saya salah baca dan mengira bahwa hanya titik terjauh dan terdekat dari $P$ saja yang harus bewarna sama, tetapi $P$ nya sendiri boleh memiliki warna yang berbeda dengan kedua titik tersebut. Untuk kasus tersebut, sepertinya cukup sulit, dan apabila saya memiliki waktu untuk mengerjakannya kembali, saya akan menuliskan solusi saya untuk variasi tersebut.