Problem

Source: Romania IMO TST 1990 p8

Tags: combinatorics, inequalities, function



For a set $S$ of $n$ points, let $d_1 > d_2 >... > d_k > ...$ be the distances between the points. A function $f_k: S \to N$ is called a coloring function if, for any pair $M,N$ of points in $S$ with $MN \le d_k$ , it takes the value $f_k(M)+ f_k(N)$ at some point. Prove that for each $m \in N$ there are positive integers $n,k$ and a set $S$ of $n$ points such that every coloring function $f_k$ of $S$ satisfies $| f_k(S)| \le m$