➕➖ mathy ➗✖️

Welcome!✌ I write math stuff here.

☀️

🌒

Latin Standard

Libertinus

Soal Kombinatorika dari Pelatnas Malaysia 2022

Published on 3 January 2023

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 (Original; English)

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$?

Problem Statement (Indonesian)

Misal $S$ adalah sebuah kumpulan $2023$ titik pada bidang, dan diketahui bahwa jarak setiap pasang titik di $S$ berbeda. Ivan mewarnai titik-titik tersebut dengan $k$ buah warna sedemikian sehingga untuk setiap titik $P \in S$, titik terjauh dan titik terdekat dari $P$ yang merupakan anggota $S$ juga memiliki warna yang sama dengan $P$.

Berapa nilai maksimum yang mungkin dari $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.

Solusi (English)

Getting the bound

Consider a directed graph $G$, each vertex represents a point of $\mathcal{S}$ and we connect two vertices $a \rightarrow 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 \rightarrow q \rightarrow 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 $\mathcal{C}$ has its furthest point in a different connected component, there are at least four points with colour $\mathcal{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 $\mathcal{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 \rightarrow 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 \rightarrow 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 \ge 4(k-1)+3 \implies 506 \ge k. \]

Proving the bound is optimal by construction

Put three points $A(-1,0), B(1,0), C(2,0)$ and construct two circles with center $A$ and $B$, each with radius $2$. We colour $A, B,$ and $C$ with the same colour. Consider a circle $\Gamma$ with center on the $x$-axis and on the line connecting the centers of the two small circles, that intersect them (the small circles are symmetric w.r.t. $x$-axis). Pair the remaining $2020$ points, there are $1010$ such pairs, and put half of the pairs to the arc of $\Gamma$ inside the top small circle, and the rest to the arc of $\Gamma$ inside the bottom one (each pair is diametrically opposite to another pair in the top circle, so they are the furthest from that pair). Points in each pair lie very close to each other, so they are the closest to each other. Each pair of points in the top small circle will correspond to another pair of points in the bottom circle as their furthest points, and the four points from these two pairs will have the same colour, so there are $1010/2 + 1 = 506$ colours.

Terima kasih sudah membaca, dan sampai jumpa di post berikutnya!