Let $A$ be a set of $2k$ points in $\mathbb{R}^n$ such that no open set in $\mathbb{R}^n$ of diameter $2$ contains more than $k$ of these points. What is the largest possible distance $r_n>0$ one can guarantee so that for all $k$ we can pair up $2k$ points under the mentioned condition so that each pair of points is at least $r_n$ apart? It is not difficult to show that $1\leq r_n \leq 2$ ($2$ comes from just taking $A=2$ and proving that one can always have them at distance $1$, one can build a distance graph so that two point from $A$ are joined if they are at least $1$ apart  such graph has minimum degree at least $k$ and so has a Hamilton cycle).

1$\begingroup$ Should there be a relation between $n$ and $k$? $\endgroup$ – François G. Dorais♦ Oct 3 '13 at 14:07

$\begingroup$ And I suppose $n$ in $\mathbb{R}^n$ is not the same $n$ which is the maximal number of points in an open set of diameter 2? $\endgroup$ – DmitryZ Oct 3 '13 at 16:13

$\begingroup$ Sorry, Dmitry, this was a misprint  n has no relation to the number of point and the condition imposed on the set A. Francois: there is no relation between $n$ and $k$. $\endgroup$ – TOM Oct 3 '13 at 20:12

$\begingroup$ I think the confusion might be, writing $r_n$ seems to imply that this value should have no dependence on $k$. Do you want, for fixed $n$, the largest possible $r_n$ that holds for every possible $k$? $\endgroup$ – usul Oct 3 '13 at 21:35

$\begingroup$ Yes, for the last comment. $\endgroup$ – TOM Oct 4 '13 at 19:35
Consider a regular $2k1$gon of diameter $2$, meaning the distance between the two most distant vertices is $2$. Then only $k1$ vertices can be in any set of diameter less than two, becsuse any set of $k$ vertices contains a maximumdistance pair. So the set of vertices plus the center form a set satisfying your condition. As $k$ goes to $\infty$, the polygon approaches a circle of radius $1$, so $r_n=1$ for $n\geq 2$.