Results 1 to 9 of 9

Math Help - filling a square with circles

  1. #1
    Junior Member
    Joined
    Apr 2010
    Posts
    33

    filling a square with circles

    I found this problem on Charles Chapman book, Real Mathematical Analysis:

    Given epsilon>0, prove that finitely many disjoint circles can be draw inside the unit square so that the total area of the discs exceeds 1 - epsilon.

    The first idea that comes to my mind is to try to fill the square with ever smaller disks of the same size. But the problem with this approach is that the total area covered by the disks is always the same! It will not change as you decrease the size of the disks.

    So all the disks cannot be of the same size. I need a new strategy. Any ideas?

    By the way, this is all in the plane. Maybe it can be extended to more dimensions, but I will be satisfied with a solution in 2D.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Feb 2010
    Posts
    147
    Quote Originally Posted by becko View Post
    I found this problem on Charles Chapman book, Real Mathematical Analysis:

    Given epsilon>0, prove that finitely many disjoint circles can be draw inside the unit square so that the total area of the discs exceeds 1 - epsilon.

    The first idea that comes to my mind is to try to fill the square with ever smaller disks of the same size. But the problem with this approach is that the total area covered by the disks is always the same! It will not change as you decrease the size of the disks.

    So all the disks cannot be of the same size. I need a new strategy. Any ideas?

    By the way, this is all in the plane. Maybe it can be extended to more dimensions, but I will be satisfied with a solution in 2D.
    Is this a measure theory question? Are you familiar with Vitali covering lemma? If not, then ignore the rest of what I'm about to say.

    Let S be the unit square. Let T be a square contained in S such that the area of T is 1 -  \frac{\epsilon}{2}

    Let V = {closed balls  B \in S ; such that  B \cap T \neq \emptyset}

    Then V is a Vitali cover of T.

    By the Vitali Covering Lemma, for all  \delta > 0 there exists countably many disjoint balls   B_i \in V such that if  U = \bigcup(B_i) , then m(T\U) = 0 and  m(U) \leq m(T) + \delta .

    Thus, it can be showed we can find finitely many of the balls  B_i such that if W is there union then m(T\W) <  \frac{\epsilon}{2}.

    And the answer will follow
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2010
    Posts
    33
    Thanks. But I'm looking for something a little more elementary than that, just using basic analysis, limits, sequences, exhaustion, things like that. The problem is from the first chapter of the book.

    Vitali is only mentioned on the 6th chapter on Lebesgue integration. So I'm sure a more elementary answer can be given.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Feb 2010
    Posts
    147
    Quote Originally Posted by becko View Post
    Thanks. But I'm looking for something a little more elementary than that, just using basic analysis, limits, sequences, exhaustion, things like that. The problem is from the first chapter of the book.

    Vitali is only mentioned on the 6th chapter on Lebesgue integration. So I'm sure a more elementary answer can be given.
    No Problem, I had a feeling.

    I wold think the answer has to to with breaking the square up into smaller and and smaller squares, each of which contains its own circle, and you could keep doing this ... If I can better formalize it I will.

    On another unrelated, but possibly interesting (only to me) note. The author of that book, Pugh, was once my prof.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2010
    Posts
    33
    I think that breaking the square into smaller squares, each of which contains its own circle, will lead you astray, as it did me. If each square contains its circle and doesnt intersect other circles, then the ratio of area covered to the area of the square remains fixed, no matter what size you make the small squares.

    We need a different strategy. A circle must be allowed to penetrate into the squares that circumscribe neighboring circles.

    By the way, I think I saw somewhere that the circles of someone (name of important person here) do this. I just can't remember where I saw this, and what was the name of the mathematician.

    So you studied with Pugh. Can you share something about him? Was he a good teacher in person? I think the book is pretty good.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Feb 2010
    Posts
    147
    Quote Originally Posted by becko View Post
    I think that breaking the square into smaller squares, each of which contains its own circle, will lead you astray, as it did me. If each square contains its circle and doesnt intersect other circles, then the ratio of area covered to the area of the square remains fixed, no matter what size you make the small squares.

    We need a different strategy. A circle must be allowed to penetrate into the squares that circumscribe neighboring circles.

    By the way, I think I saw somewhere that the circles of someone (name of important person here) do this. I just can't remember where I saw this, and what was the name of the mathematician.

    So you studied with Pugh. Can you share something about him? Was he a good teacher in person? I think the book is pretty good.
    OK prof. I hardly remember to be honest

    I don't think I was clear in what I said. I meant something like start with the biggest possible circle in the square. Then look at the uncovered regionS and break them down in the largest squares possible and put circles in them and keep doing that....
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by becko View Post
    By the way, I think I saw somewhere that the circles of someone (name of important person here) do this. I just can't remember where I saw this, and what was the name of the mathematician.
    You must be referring to Apollonian packings of circles. You can also do it in a square: first the inscribed circle and then Apollonian packings in each of the four corners (there is a figure in Falconer, "Techniques in fractal geometry", p.55 (if your library has it) but no proof).

    It is true that the measure of the complement goes down to 0 as we add circles. This implies your result: choose a subset of discs whose complement has measure less than \epsilon/2. Then reduce the radius of the n-th circle ( n\geq 1) so that its area is reduced by \frac{\epsilon}{2^{n+1}} (or delete the circle if this is larger than the initial area). Then the circles become disjoint, and the area of their complement is less than \frac{\epsilon}{2}+\sum_{n\geq 1}\frac{\epsilon}{2^{n+1}}=\epsilon.

    It is however not obvious that the measure of the complement goes down to 0 as the number of circles increases. This doesn't follow from a "general argument". You can find a very nice proof here, but I don't think your book expects you to think of that. So I don't know what it may be expecting.

    Another proof can be derived from the proof that the Hausdorff dimension of the complement is strictly less than 2, which you can find in Falconer, "The geometry of fractal sets" p 125-131 (it follows a paper by Hirst) but this proof is more advanced (and much more computational).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Apr 2010
    Posts
    33
    I think I know a solution now (got the idea here: Art of Problem Solving &bull; View topic - filling a square with circles). It goes like this:

    (I assume that squares can cover any area as tightly as needed by making the squares smaller and more numerous. After this proof, the same follows for circles.)

    Let s be the supremum of the areas that can be covered by finitely many disjoint discs inside the unit square. Take \tau >0 and let A be a packing of disjoint discs inside the unit square whose total area is s-\tau . The complement of this packing can be nearly filled with finitely many disjoint squares, leaving an area \delta uncovered, which can be made as small as we want by making the squares smaller. Inside each of these squares we can repeat the packing A. Then the total area covered by the circles will be:

    s-\tau +(s-\tau )(1-s+\tau -\delta )

    (EDIT: fixed this. The -delta was outside the parenthesis, but it should be inside)

    If we make \tau \rightarrow 0 and \delta \rightarrow 0, the result should be the supremum s, so we have the equation:

    s+s(1-s)=s

    which implies s=1. This completes the proof.
    Last edited by becko; April 27th 2010 at 02:05 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by becko View Post
    I think I know a solution now (got the idea here: Art of Problem Solving &bull; View topic - filling a square with circles). It goes like this:
    Nice proof. Matching this idea very closely gives: for any \varepsilon>0,\delta>0, we have s\geq s-\varepsilon+(1-s-\delta)c where c=\frac{\pi}{4} is the area of the disc inscribed in a unit square (or the area of any disc(s) in this square) (Indeed, an area A_0\geq s-\varepsilon is filled with circles initially, and an area A_1\geq(1-A_0-\delta)c of the complement as well, hence a total area A_0+A_1\geq s-\varepsilon+(1-A_0-\delta)c\geq s-\varepsilon+(1-s-\delta)c since A_0\leq s, and A_0+A_1\leq s by definition of s). Letting \varepsilon,\delta\to 0, we get s\geq s+(1-s)c, hence (1-s)c=0 and finally s=1.
    Last edited by Laurent; April 27th 2010 at 12:23 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: June 15th 2011, 03:06 AM
  2. proving homeomorphisms, circles, torus, square
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: March 15th 2011, 04:49 PM
  3. Pipe Filling
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 28th 2011, 09:03 AM
  4. Circles within a square
    Posted in the Geometry Forum
    Replies: 5
    Last Post: April 29th 2010, 12:58 PM
  5. Two circles and a square
    Posted in the Geometry Forum
    Replies: 2
    Last Post: January 12th 2010, 04:03 PM

Search Tags


/mathhelpforum @mathhelpforum