Author |
Topic: Cover the plane with strips. (Read 1630 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Cover the plane with strips.
« on: Mar 13th, 2005, 9:41am » |
 Quote  Modify
|
We are dealing with the 2-D plane.
A strip is defined as a the region between two parallel lines(including the points on the lines). The width of a strip is the distance between the two parallel lines.
Suppose we are given a sequence of widths w1, w2, ... , wn... such that w1 + w2 + ... + wn -> w (a finite positive real). Can we find a set of strips S1, S2, ... , Sn... with strip Si having width wi, such that the strips cover the whole plane? (i.e every point of the plane is in some strip)
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Cover the plane with strips.
« Reply #1 on: Mar 14th, 2005, 9:05am » |
Quote Modify
|
This seems totally impossible at the first sight... But this is not unusual when dealing with infinite (and here the infinity is 2-fold).
Let me ask this question: Is it the case that if the task is impossible when strips are parallel to each other, then it's impossible when they intersect?
BTW, Aryabhatta, do you know the answer?
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Cover the plane with strips.
« Reply #2 on: Mar 14th, 2005, 9:26am » |
Quote Modify
|
Consider the closed ball Bn of radius n centered at the origin. If we have a strip of width w_1 then certainly the measure (i.e. area) of the intersection of Bn with the strip of width w_1 cannot exceed 2nw_1. Now if we let S denote the union of all the strips and S_i the ith strip, then mu(S intersect Bn) <= \sum mu(S_i intersect B_n) < \sum 2nw_i = 2nw, where mu denotes Lebesgue or Jordan measure (the sets in question are nice enough so that the two coincide). But mu(B_n)=pi * n^2, so for n sufficiently large we have that mu(B_n)> mu(S intersect B_n), which can only be the case if S does not cover B_n. Hence the strips cannot cover the entire plane since they fail to cover some subset of the plane.
Note that this proof deals with the "infinity" at hand by reducing the problem to very large "finite" questions, and proving that if we interpret "finite" to be large enough then the plane already cannot be covered.
|
| « Last Edit: Mar 14th, 2005, 9:29am by Obob » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Cover the plane with strips.
« Reply #3 on: Mar 14th, 2005, 10:00am » |
Quote Modify
|
on Mar 14th, 2005, 9:05am, Barukh wrote:This seems totally impossible at the first sight... But this is not unusual when dealing with infinite (and here the infinity is 2-fold).
Let me ask this question: Is it the case that if the task is impossible when strips are parallel to each other, then it's impossible when they intersect?
|
|
I don't know the answer to that question.
I know an answer to the original question though...
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Cover the plane with strips.
« Reply #4 on: Mar 14th, 2005, 10:03am » |
Quote Modify
|
Well done Obob. I had the same solution in mind.
|
| « Last Edit: Mar 15th, 2005, 9:42am by Aryabhatta » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Cover the plane with strips.
« Reply #5 on: Mar 14th, 2005, 1:29pm » |
Quote Modify
|
Here's a somewhat interesting (although admittedly very easy) follow up question: if {w_n} is a sequence of reals such that \sum w_i converges, can we find a sequence of strips S_i which "almost" cover the plane, in the sense that for every point x and every epsilon>0 there exists some point y lying in some strip which is less than epsilon away from x?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Cover the plane with strips.
« Reply #6 on: Mar 15th, 2005, 12:54am » |
Quote Modify
|
I think you can! place the strips vertically, each centered on the set {(x,y) where x=pi/qi}, where the pi/qi are an exhaustive enumeration of the rationals.
Considering that the strips have non-zero width, you really may wonder how the strips can fail to cover the whole plane.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Cover the plane with strips.
« Reply #7 on: Mar 15th, 2005, 6:31am » |
Quote Modify
|
Grimbal, that's absolutely cool! 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Cover the plane with strips.
« Reply #8 on: Mar 15th, 2005, 9:41am » |
Quote Modify
|
on Mar 15th, 2005, 12:54am, Grimbal wrote:I think you can! place the strips vertically, each centered on the set {(x,y) where x=pi/qi}, where the pi/qi are an exhaustive enumeration of the rationals.
Considering that the strips have non-zero width, you really may wonder how the strips can fail to cover the whole plane.
|
|
Well done Grimbal.
To clarify, this is a solution to Obob's follow up question. Grimbal's construction works because the rationals form a dense subset of the reals.
To answer Grimbal's other question: How does this example not give a construction which covers the whole plane?
Intuitively it seems like it must be true, but suppose given the point (x,0), x irrational, we want to find the strip that contains it. Say r is a rational close to x. Now the strip at r could have a width < |r-x|/2. So we move to a rational r' closer than r, the strip around r' could still have length < |r'-x|/2 and so on. This could happen as the sum of the widths of the strips is finite, the strips keep getting thinner and thinner.
Anyway for a proof:
It is enough is we consider the line y=0. Now we are dealing with reals. So we are given a set on widths wn, we define an It centered at rt, It being of width wt. r1, r2,...,rn,.. being an enumeration of the rationals.
Also, [sum]wn is finite.
The result follows immediately from the countable sub additivity of the lebesgue measure. (Sum of measures of the intervals is at least the measure of the union)
But the argument would probably be more convincing if we could come up with a set of intervals In for which we can demonstrate existence of a real x not lying in the union.
Wlog assume that the total sum of widths is < 1/4 and we are dealing with the interval [0,1]. Now, whichever way we place In around rn, consider a corresponding _open_ interval Jn around rn which is twice the length of In and contains In.
The sum of lengths of Jn is no more than 1/2. Now if these intervals cover the interval [0,1], by the Heine Borel theorem (Every open cover of a closed set has a finite sub cover), there is a finite number of Ji's which cover [0,1]. We can easily see that if the sum of lengths of a _finite_ number of intervals in < 1, they cannot cover a closed interval of length 1.
Maybe a concrete example would be better. I right now can't think of any, will post one when I can think of one.
|
| « Last Edit: Mar 15th, 2005, 2:52pm by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Cover the plane with strips.
« Reply #9 on: Mar 15th, 2005, 3:05pm » |
Quote Modify
|
Ok. A concrete example which uses the following theorem:
http://mathworld.wolfram.com/LiouvillesApproximationTheorem.html
For any algebraic number x of degree t >= 2, only finitely many rational p/q exist such that |x - p/q| < 1/qt.
(Degree of algebraic number x = degree on minimum degree polynomial with rational coefficients of which it is a root).
So pick one such number x of degree say 100. Find all r/s such that |x - r/s| < 1/s100. Let 0 < d < min { |x - r/s|}. Now for each rational number rn = pn/qn take an interval of length min {d/2,1/2qn100} around it.
The number x is not covered by any such interval. The sum of lengths of these intervals is definitely > 0 (in fact most likely it is infinite).
|
| « Last Edit: Mar 15th, 2005, 3:07pm by Aryabhatta » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Cover the plane with strips.
« Reply #10 on: Mar 15th, 2005, 3:59pm » |
Quote Modify
|
Here's another example which is perhaps more concrete:
For each dyadic rational x in (0,1), say x = (2m+1)/2k, and take the neighborhood Ux = ( (16m+7)/2k+3, (16m+9)/2k+3 ). Thus if x = 0.a1 (in binary), we take the interval (0.a0111, 0.a1001). Note that any number in this interval has at least 3 consecutive 1s or 0s in its binary expansion. Thus the union of these intervals contains all dyadic rationals, but misses uncountably many elements of (0,1). (For example, it misses 1/3, as well as 0.0010011011...)
Essentially, any point in one of these intervals can be approximated "well" by some dyadic rational, but a number like 1/3=0.010101... can't. This is similar to Aryabhatta's example above, which uses the fact that an algebraic number can't be approximated "too well" by rationals.
Moreover, by taking intervals (0.a0111...11, 0.a1000...01), where the length of the "..." increases appropriately with the length of a, the union can be made to have arbitrarily small measure.
If we are given prescribed widths for the intervals wi, enumerate the rationals q0,q1,..., and pick your favorite irrational e.
Now for each i, pick the first j not yet chosen with |qj-e|>wi/2, and take an interval of width wi around qj.
As long as wi -> 0, every qj will get used. For, once {q0,...,qj-1} have all been used, qj will get passed over only finitely many times after that. This will give intervals centered at each rational whose union misses e.
In fact, if [sum] wi is infinite, one can find intervals with those lengths whose union is precisely the complement of any given point.
Suppose [sum] wi is infinite, and wi -> 0.
What are necessary and sufficient conditions on U, for U to be a union of intervals of lengths wi? Hint: It's the obvious thing.
|
| « Last Edit: Mar 15th, 2005, 5:16pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print