6
$\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$
  • $\begingroup$ the "boundary of a circle"??? $\endgroup$ – YCor Nov 2 '18 at 22:55
5
$\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 https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Cleary-Morris-Yost260-275.pdf

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

The answer is "yes".

Arguing by contradiction assume there is no such number. By 1-dimesional Helly's theorem, there is a pair of point-arrays $\{x_1,\dots,x_n\}$ and $\{y_1,\dots,y_m\}$ such that for their average distance functions $f(z)=\tfrac1n\cdot\sum_i|x_i-z|$ and $h(z)=\tfrac1m\cdot\sum_j|y_j-z|$, 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}|x_i-y_j|=\tfrac1n\cdot\sum_ih(x_i),$$ a contradiction.

| cite | improve this answer | |
$\endgroup$
  • $\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 '18 at 3:00
  • 1
    $\begingroup$ @erz it is 1-dimesional Helly's theorem. $\endgroup$ – Anton Petrunin Nov 2 '18 at 3:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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