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.

Consider $\mathbb{R}^n$ and its usual Euclidean norm given by the distance $d(x,y) = \sqrt{\sum_{i=1}^n (x_i-y_i)^2}$.

Let $B(y,1) = \{ x\in \mathbb{R}^n : d(x,y) \leq 1 \}$ be the closed 1-ball around $y$ and $B(0,2) = \{x\in \mathbb{R}^n: d(x,0) \leq 2 \}$ be the 2-ball centered at the origin.

How many 1-balls do you need to cover (contain) the 2-ball?


share|improve this question
    
(Unhelpful) claim: At least 4 –  Matt Feb 4 '12 at 17:48
    
@Matt At least $2^n$, comparing volumes in $\mathbb{R}^n$. –  alex.jordan Feb 4 '12 at 21:25
    
For $n=2$, $7$ will do it and no fewer. You can prove that you need at least $6$ just to cover the circumference. And there is only one configuration of $6$ that will cover the circumference, up to rotation. You need at least one more to cover the origin, and as it turns out, making the $7$th centered at the origin will leave everything covered. –  alex.jordan Feb 5 '12 at 22:11
add comment

3 Answers

up vote 5 down vote accepted

There's a lower bound of $2^n$ that comes immediately from volume considerations. For fixed $n$ I'm not sure when the upper bound is known exactly (this seems uncomfortably close to the Kepler conjecture, which was hard even in $3$ dimensions), but there's asymptotic results for covering space (or spheres of growing radii) by spheres going back to Rogers ("A Note on Coverings", 1957...see also this paper of Ilya Dumer) that might be able to get you something like $3^n n \log n$. I'm not familiar enough with this area to say if there's more specific results pertaining to your problem.

A quick (not at all optimal, and not my own, though I don't know a source to give for it) argument can get you a bound of $5^n$. Consider the following process: Place balls of radius $1/2$ centered at $x_1, x_2, \dots$ in the larger sphere, subject only to the constraint that no two of these balls intersect (these balls can lie partially outside the sphere, but they must be centered inside the sphere). Continue placing these balls in an arbitrary fashion until no more such balls can be placed.

At this point all the balls you have placed are disjoint and lie in a sphere of radius $5/2$ (the extra $1/2$ coming from balls which are centered near the edge of the original sphere). Therefore there are at most $5^n$ balls placed. Furthermore, each point in the sphere is within $1$ of one of your ball's centers, since otherwise you could fit another ball of radius $1/2$ in. So replacing your radius $1/2$ balls with radius $1$ balls with the same center gives you a covering.

share|improve this answer
add comment

Here is a rough upper bound: if $x_n$ is the number of $n$-balls of radius $1$ necessary to cover the $n$-ball of radius $2$, then $$x_n\leq \left\lceil \vphantom{\large |} 2\sqrt{n}\right\rceil^n .$$ Consider that the $n$-ball of radius $2$ can be inscribed in the $n$-cube of side length $4$. The largest $n$-cube that can be inscribed in the $n$-ball of radius $1$ has a $n$-space diagonal of $2$, and therefore has side length $\frac{2}{\sqrt{n}}$. Thus, we would need $$\left\lceil \frac{\quad 4\quad}{\frac{2}{\sqrt{n}}} \right\rceil=\left\lceil \vphantom{\large |} 2\sqrt{n}\right\rceil$$ edges of the smaller $n$-cubes to completely cover an edge of the larger $n$-cube, and hence we would need $$\left\lceil \vphantom{\large |} 2\sqrt{n}\right\rceil^n$$ of the smaller $n$-cubes to cover the larger $n$-cube, thereby also covering the $n$-ball of radius $2$. Since each $n$-ball of radius $1$ contains one of these smaller $n$-cubes, we can therefore use this number of $n$-balls of radius $1$ to cover the $n$-ball of radius $2$.

share|improve this answer
add comment

In $\mathbb{R}^2$ it's 7.

It's sufficient because:

You can take the circum-disks of the cells in a hexagonal grid as your small disks (http://mathworld.wolfram.com/HexagonalGrid.html). It's easy to see that a disk of radius 2, centered at the center of one hexagon, will intersect exactly 7 hexagons, and so the union of the circum-disks of those hexagons (which have radius 1) covers the disk of radius 2.

It's necessary, because: Any covering of the big disk must also cover its boundary. If you use the 6 disks as in the hexagonal arrangement, then they never overlap on the boundary, and the part of the arc covered by each one is maximal, this means that fewer than 6 disks won't be enough to cover the boundary. Then, since any disk that contains the origin will at most intersect the boundary in a single point, none of our 6 boundary disks can contain the origin, and thus an additional one is needed.

share|improve this answer
add comment

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.