wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Cover the plane with strips.
        
(Message started by: Aryabhatta on Mar 13^th, 2005, 9:41am)

Title: Cover the plane with strips.
Post by Aryabhatta on Mar 13^th, 2005, 9:41am

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 w₁, w₂, ... , w_n... such that w₁ + w₂ + ... + w_n -> w (a finite positive real). Can we find a set of strips S₁, S₂, ... , S_n... with strip S_i having width w_i, such that the strips cover the whole plane? (i.e every point of the plane is in some strip)

Title: Re: Cover the plane with strips.
Post by Barukh on Mar 14^th, 2005, 9:05am

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?

Title: Re: Cover the plane with strips.
Post by Obob on Mar 14^th, 2005, 9:26am

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.

Title: Re: Cover the plane with strips.
Post by Aryabhatta on Mar 14^th, 2005, 10:00am

on 03/14/05 at 09:05:03, Barukh wrote:

I don't know the answer to that question.
I know an answer to the original question though...

Title: Re: Cover the plane with strips.
Post by Aryabhatta on Mar 14^th, 2005, 10:03am

Well done Obob. I had the same solution in mind.

Title: Re: Cover the plane with strips.
Post by Obob on Mar 14^th, 2005, 1:29pm

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?

Title: Re: Cover the plane with strips.
Post by Grimbal on Mar 15^th, 2005, 12:54am

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.

Title: Re: Cover the plane with strips.
Post by Barukh on Mar 15^th, 2005, 6:31am

Grimbal, that's absolutely cool! :D

Title: Re: Cover the plane with strips.
Post by Aryabhatta on Mar 15^th, 2005, 9:41am

on 03/15/05 at 00:54:51, Grimbal wrote:

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 w_n, we define an I_t centered at r_t, I_t being of width w_t. r₁, r₂,...,r_n,.. being an enumeration of the rationals.

Also, [sum]w_n 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 I_n 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 I_n around r_n, consider a corresponding _open_ interval J_n around r_n which is twice the length of I_n and contains I_n.

The sum of lengths of J_n 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 J_i'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.

Title: Re: Cover the plane with strips.
Post by Aryabhatta on Mar 15^th, 2005, 3:05pm

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/q^t.

(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/s¹⁰⁰. Let 0 < d < min { |x - r/s|}. Now for each rational number r_n = p_n/q_n take an interval of length min {d/2,1/2q_n¹⁰⁰} 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).

Title: Re: Cover the plane with strips.
Post by Eigenray on Mar 15^th, 2005, 3:59pm

Here's another example which is perhaps more concrete:
For each dyadic rational x in (0,1), say x = (2m+1)/2^k, and take the neighborhood U_x = ( (16m+7)/2^k+3, (16m+9)/2^k+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 w_i, enumerate the rationals q₀,q₁,..., and pick your favorite irrational e.
Now for each i, pick the first j not yet chosen with |q_j-e|>w_i/2, and take an interval of width w_i around q_j.
As long as w_i -> 0, every q_j will get used. For, once {q₀,...,q_j-1} have all been used, q_j 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] w_i is infinite, one can find intervals with those lengths whose union is precisely the complement of any given point.

Suppose [sum] w_i is infinite, and w_i -> 0.
What are necessary and sufficient conditions on U, for U to be a union of intervals of lengths w_i? Hint: It's the obvious thing.