Let $S$ be the set of points inside and on the boarder of a regular haxagon with side length 1. Find the least constant $r$, such that there exists one way to colour all the points in $S$ with three colous so that the distance between any two points with same colour is less than $r$.
Problem
Source: China TST 2003
Tags: inequalities, real analysis, combinatorics unsolved, combinatorics
27.07.2006 18:12
I believe it's $\frac{3}{2}$. First of all, in order to construct an example, let $ABCDEF$ be the hexagon, and let $O$ be its center. Draw three segments connecting $O$ to the midpoints $M,N,P$ of $AB,CD,EF$ respectively. This divides the hexagon into three regions, which will be the regions we color. On the borders, where the sets overlap, choose an arbitrary color, except in the points $M,N,P$, which we color differently (so that the inequality is strict: every two points having the same color are strictly less than $\frac{3}{2}=MN=NP=PM$ apart). Conversely, we’ll prove that the intersection of one of the colored regions with the border of the hexagon contains points $X_{n},Y_{n}$ such that $\limsup\angle X_{n}OY_{n}\ge\frac{2\pi}3$ (I’m referring to the angle $\angle X_{n}OY_{n}\le\pi$). Since two points $U,V$ on the border of the hexagon such that $\angle UOV=\frac{2\pi}3$ are clearly at least $\frac{2}{3}$ apart, this will suffice for the converse. Since we’re now only dealing with angles, we may as well replace the hexagon with the unit circle. We can also assume that the circumference of the circle is covered with three closed sets $\mathcal S_{i},\ i=\overline{1,3}$. Our aim will now be to show that in these conditions, there are two points $X,Y$ belonging to the same set $\mathcal S_{i}$ such that $\angle XOY\ge\frac{2\pi}3$. The conclusion will follow. Assume the contrary, and take an arbitrary $P\in\mathcal S_{i}$. Then $\mathcal S_{i}$ must be contained in the union $\mathcal S$ of the two arcs of length $\frac{2\pi}3$ having $P$ as an endpoint. Now let $Q\in\mathcal S_{i}$ be one of the (at most two) points farthest away from $P$ (there is at least one such point because $\mathcal S_{i}$ are closed). All the other points of $\mathcal S_{i}$ must lie withing the arc of length $\frac{2\pi}3$ starting at $Q$ and contained completely in $\mathcal S$. We’ve shown that each $\mathcal S_{i}$ is contained strictly in an arc of length $\frac{2\pi}3$. Since the $\mathcal S_{i}$ are closed, we conclude that each one has measure (the Lebesgue measure on the circle, with totale size $2\pi$) strictly less than $\frac{2\pi}3$, and this contradicts the fact that the three sets cover the circumference, which has measure $2\pi$. We have our contradiction.