9
$\begingroup$

If $X$ is a connected, compact metric space with distance function $d : X^2 \rightarrow \mathbb{R}^+$, is it true that there exists a positive real number $a$, dependent on $X$ and $d$, such that for any $n$ and for any $x_1, x_2, \cdots, x_n \in X$, there exists $y$ such that $$\frac{1}{n}\left(d(x_1,y) + d(x_2,y) + \cdots + d(x_n,y)\right) = a?$$

Motivation: trivial when $X$ is the boundary of a circle, a tricky contest problem when $X$ is the boundary of a square (these examples all use Euclidean distance)

$\endgroup$
1
  • $\begingroup$ the "boundary of a circle"??? $\endgroup$
    – YCor
    Nov 2, 2018 at 22:55

2 Answers 2

6
$\begingroup$

It's a classic theorem of O. Gross from 1964. The number $a$ is also unique for a given space $(X,d)$.

There is an exposition at Cleary and Morris - Numbers for shapes.

The original paper is: O. Gross, "The rendezvous value of a metric space", Advances in Game Theory, Ann. of Math. Studies no. 52, Princeton, 1964, 49–53.

$\endgroup$
5
$\begingroup$

The answer is "yes".

Arguing by contradiction assume there is no such number. By 1-dimensional Helly's theorem, there is a pair of point-arrays $\{x_1,\dotsc,x_n\}$ and $\{y_1,\dotsc,y_m\}$ such that for their average distance functions $f(z)=\tfrac1n\cdot\sum_i\lvert x_i-z\rvert$ and $h(z)=\tfrac1m\cdot\sum_j\lvert y_j-z\rvert$, we have $$f(p)>h(q)$$ for any two points $p$, $q$.

Note that $$\tfrac1m\cdot\sum_if(y_i)=\tfrac1{m\cdot n}\cdot\sum_{i,j}\lvert x_i-y_j\rvert=\tfrac1n\cdot\sum_ih(x_i),$$ a contradiction.

$\endgroup$
2
  • $\begingroup$ Why is it enough to consider only two sets $X$ and $Y$? By compactness it is possible to choose a finite number, but how do you reduce it to two? $\endgroup$
    – erz
    Nov 2, 2018 at 3:00
  • 1
    $\begingroup$ @erz it is 1-dimesional Helly's theorem. $\endgroup$ Nov 2, 2018 at 3:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.