Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Question: Let $(X, d)$ be a metric space such that there is a positive $a$ and $n$ open balls $B(x_1, a),\ldots, B(x_n, a)$ such that together these balls cover $X$.

Find an upper bound $M$ for the diameter of $X$. Find "the smallest" upper bound $M$ for the diameter of $X$ in the following sense: the formula for $M$ is valid in all cases, and there is a metric space $X$ such that $\operatorname{diam} (X) = M$.

Thoughts: I find the question a little hard to parse. I think it's asking what is the biggest diameter that this can have, so my answer then would be $\sup M = an$.

Thinking about the real number line, if there are $n$ # of balls, the two furthest points from each other would be $a\cdot n$ length from each other. Still trying to figure out what the rest of the questions asks...

share|improve this question
    
Thank you for your input! I think I don't quite understand that... the $max d(x_j,x_k)$ would be $a(n-2) + (a/2) + (a/2) = a(n-1)$ but $2a + a(n-1) = a(n+1)$ which doesn't intuitively make sense to me. Am I thinking about this incorrectly? If you take a closed, bounded interval of R, and line up the balls to cover that set you get that the distance between two points could be at most $a\times n$. I can't picture a bigger distance than that right now. –  lillian Oct 9 '11 at 17:25
1  
Suppose $X$ has $n$ points, with any two points being a fixed distance $d$ apart. Then $X$ has diameter $d$, but can be covered by $n$ open balls with radius as small as we like. So there's no function of $n$ and $a$ which will work as an upper bound here. –  Chris Eagle Oct 9 '11 at 17:38
    
I've been assuming that "a" is a fixed radius but I think it is too ambiguously written to know either way. Thanks for the input, I think I need further direction to understand how to think about this problem. –  lillian Oct 9 '11 at 17:41
1  
The radius $a$ is fixed. The question is not at all ambiguous: it’s asking for the smallest number (as a function of $a$ and $n$ that is guaranteed to be at least as large as the diameter of $X$. Then, once you have that, you’re to find a specific example of $n$ balls of radius $a$ covering a space whose diameter really is that big; this will show that no smaller number would have met the guarantee. –  Brian M. Scott Oct 9 '11 at 17:50
    
If $X$ is not connected, then there is no upper bound from the information given. –  robjohn Oct 9 '11 at 17:52

1 Answer 1

Let $x,y\in X$. Then we can find $j,k\in\{1,\ldots,n\}$ such that $d(x,x_k)<a$ and $d(y,x_j)<a$. We get $$d(x,y)\leq d(x,x_k)+d(x_k,x_j)+d(x_j,y)< a+d(x_k,x_j)+a\leq 2a+\max_{1\leq j,k\leq n}d(x_k,x_j),$$ therefore $\displaystyle \operatorname{Diam}(X)\leq 2a+\max_{1\leq j,k\leq n}d(x_k,x_j)$. We can't hope a better bound. Indeed, taking $X:=\left]0,(n+1)a\right[$ with the usual metric, and $x_j=ja$, we get that $\displaystyle X=\bigcup_{j=1}^nB(x_j,a)$, $\operatorname{Diam}(X)=(n+1)a$ and $\displaystyle \max_{1\leq j,k\leq n}d(x_k,x_j)=\max_{1\leq j,k\leq n}|ka-ja|=(n-1)a$, and the above inequality is an equality.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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