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

        riddles >> medium >> A Rectangle with Room...
        
(Message started by: JP05 on Jun 6th, 2007, 6:27pm)
Title: A Rectangle with Room...
Post by JP05 on Jun 6th, 2007, 6:27pm
One randomly tosses 120, 1 by 1 squares, into a rectangle 20 by 25. Show that a circle of radius 1/2 can be placed in the rectangle such that it does not have any points in common with any of the squares.
Title: Re: A Rectangle with Room...
Post by Grimbal on Jun 7th, 2007, 12:45am
One approach:
[hide]Add a 1/2 unit border to the squares, see that they still cannot cover all points.[/hide]
Title: Re: A Rectangle with Room...
Post by towr on Jun 7th, 2007, 1:25am
How about 121 squares?
Or perhaps, rather, what is the maximum number of squares you can put on the rectangle such that it is always possible to place a 1/2 radius circle without overlapping with a square.
Title: Re: A Rectangle with Room...
Post by Sir Col on Jun 8th, 2007, 12:00am
It is possible to get [hide]154[/hide]. If it is then the maximum number of 1 x 1 on an a x b rectangle is [hide][ak] * [bk], where [] is the integer part function and k = 2 - sqrt(2)[/hide].

Actually we can get [hide]180[/hide] unit squares on that grid. In which case the maximum number is [hide]([(a-1)k]+1) * ([(b-1)k]+1), where k = 2 - sqrt(2)[/hide].
Title: Re: A Rectangle with Room...
Post by Bishamon on Jun 8th, 2007, 1:16am

Quote:
Or perhaps, rather, what is the maximum number of squares you can put on the rectangle such that it is always possible to place a 1/2 radius circle without overlapping with a square.


well, i think the question that we should be looking at is "What are the minimum number of 1x1 squares that can be placed inside the rectangle such that the given circle could not fit in?". By getting a value that is greater than 120, we can prove that no matter how you arrange the squares(randomly thrown), we can get a circle to fit in.

Since, a circle of radius 0.5 should fit in the rectangle, it basically remains to find a portion of the rectangle that has 3 squares empty that are arranged in a 'L' manner as given below.

1111
1011
1001
1111


The 0's denote empty squares, and the 1's denote filled squares.


If we fill the squares up like i did below, it would require 250 1x1 squares.

010101
010101
010101
010101
010101
010101

Hence, we need at least 250(can we make it lesser than this?) 1x1 squares before we can prevent the circle from being added.
Title: Re: A Rectangle with Room...
Post by towr on Jun 8th, 2007, 2:59am

on 06/08/07 at 01:16:25, Bishamon wrote:
well, i think the question that we should be looking at is "What are the minimum number of 1x1 squares that can be placed inside the rectangle such that the given circle could not fit in?".
That's pretty much the same question, the difference would be one square.
Title: Re: A Rectangle with Room...
Post by towr on Jun 8th, 2007, 3:28am

on 06/08/07 at 01:16:25, Bishamon wrote:
Hence, we need at least 250(can we make it lesser than this?) 1x1 squares before we can prevent the circle from being added.
That makes it at most 250.

And 180 is really enough, since each square spoils at least a square area of 1+1/2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 x 1+1/2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 for any unit circles. (A figure Sir Col already gave.) So that's already at least a lower upper bound.
Title: Re: A Rectangle with Room...
Post by Bishamon on Jun 8th, 2007, 6:28am
could you please how u arrived at                                   1 + ((0.5)/sqrt2)*(1+(0.5)*sqrt2) . (Did i get this correct?)
Title: Re: A Rectangle with Room...
Post by towr on Jun 8th, 2007, 1:34pm

on 06/08/07 at 06:28:10, Bishamon wrote:
could you please how u arrived at                                1 + ((0.5)/sqrt2)*(1+(0.5)*sqrt2) . (Did i get this correct?)
It should be (1+(0.5)*http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2)*(1+(0.5)*http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2)
The way to get it is to first put a 1/2 unit border around our unit squares. Which means that the total area will consist of the square, 4 half-squares at the edges, and 4 quarter-circles at the corners.
Now, along the diagonal of this form, we have a length of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 + 1 (diagonal of the unit square + diagonal of a unit circle). This is also the diagonal of the maximum square that fits into the form. Dividing it by http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2, we get the sides of that square. And then we can figure out how many times it fits in the rectangle.

A drawing would probably be clearer, but unfortunately I'm at a different computer, without any of my drawing programs.

The question that remains is whether we can find a better way to pack the 'bordered' squares which doesn't have as much overlap.
Title: Re: A Rectangle with Room...
Post by Sir Col on Jun 9th, 2007, 3:12am
Upon further reflection I'm going to revise my previous answer (again). I'm becoming less and less confident with my solution at each revision.

As we're dealing with chance (randomly throwing squares on to the rectangle) we need to consider the worst possible situation. That is, the problem is equivalent to determining the least amount of squares necessary to make it just possible to fit a circle without touching any of the squares. Hence if one more square is added then there is no longer any guarantee that a circle will fit. In other words, we're looking for the most inefficient use of squares on the grid.

Consider the arrangement in the attached diagram.

Let the horizontal/vertical distance between the centre of the circles be x and the diagonal distance is sqrt(2)+1. Hence x=sqrt(3/2+sqrt(2))=1+sqrt(2)/2.

In a 25x20 grid we remove 1/2 from each edge and get a 24x19 grid in which we wish to evenly distribute the circle centres. 24/x~=14.06 and 19/x~=11.13. Therefore we can fit a grid of 14x11=154 circles.

Hence there will be 13x10=130 squares on the rectangle.
Title: Re: A Rectangle with Room...
Post by towr on Jun 9th, 2007, 12:53pm

on 06/09/07 at 03:12:52, Sir Col wrote:
In a 25x20 grid we remove 1/2 from each edge and get a 24x19 grid in which we wish to evenly distribute the circle centres.
Don't we wish to distribute the square-centres evenly? And shouldn't we round up?
I still get 15*12 = 180 (On exactly the pattern you posted in your picture)
Title: Re: A Rectangle with Room...
Post by Sir Col on Jun 9th, 2007, 5:28pm
My previous answer, 180, used the same pattern but with the squares starting in the top left corner.

But we are looking for the most inefficient way to place the squares. That is, we're looking for the arrangement that uses the least amount of squares so that no more circles can be added. I realised that I am able to arrange 180 squares on the rectangle so that no circle can be added and as the squares are distributed randomly, this arrangement is a possibility.

I believe that the arrangement in the diagram above is the most inefficient way to use 130 squares.

Clearly if one more square were added to each row, making an arrangement of 140 squares in total, the gaps between the squares would reduce so as to make it impossible to add a circle anywhere.

However, it is quite possible that the solution makes use of an arrangement different to the one considered here and is somewhere between 120 and 140, which is why I said in my previous post that I was becoming less and less confident with my answer.
Title: Re: A Rectangle with Room...
Post by towr on Jun 10th, 2007, 7:19am

on 06/09/07 at 17:28:15, Sir Col wrote:
My previous answer, 180, used the same pattern but with the squares starting in the top left corner.
Well, my arrangement of 180 squares did start with the circles in the top left corner. So obviously one of us miscounted.


Quote:
I believe that the arrangement in the diagram above is the most inefficient way to use 130 squares.
I don't believe 130 squares like that cover the rectangle, not even almost.

The amount of overlap between the area covered by the squares, is at least 1/2*(1/2 -1/4 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2) between each two adjacent squares. So for the 12*9 inner squares, which have four neighbours each, we get in excess of 31 unit squares of area overlap. Leaving much too little to cover the rectangle.
Title: Re: A Rectangle with Room...
Post by towr on Jun 10th, 2007, 8:17am
Here is a pdf with a vectorgraphics representation of the covering, to scale.
Title: Re: A Rectangle with Room...
Post by Grimbal on Jun 10th, 2007, 10:49am
I will take Sir Col's arrangement, but I will take a different gap for x and y.

Let's take:
sx, sy: size in x, y
nx, ny: nb of squares in x, y
dx, dy: 1/2 gap size in x, y
r = radius = 1/2
The gap on the border is one radius + 1/2 gap size.

We have:
 sx = 1/2 + nx·(dx + 1 + dx) + 1/2 = 1 + nx + 2·nx·dx.
From there
  dx = (sx - nx - 1)/(2·nx)
  dy = (sy - ny - 1)/(2·ny)

The circle fits if dx^2+dy^2 >= radius^2 = 1/4
If d = dx^2 + dy^2 < 1/4 we have an arrangement of nx·ny squares that

With sx = 20 and sy = 25, and trying different for nx and ny, we can see that the following pairs have d<0.25
  nx=10, ny=17, nx·ny=170, d=0.245
  nx=11, ny=15, nx·ny=165, d=0.222
  nx=12, ny=14, nx·ny=168, d=0.212
  nx=13, ny=13, nx·ny=169, d=0.232

  nx=19, ny=12, nx·ny=228, d=0.250 (not ok...)

One arrangement needs only 165 squares and has gaps small enough to block a 1/2-radius circle.

So, 165 is an upper bound to the minumum number of squares that can prevent a circle to be placed in the rectangle.
Title: Re: A Rectangle with Room...
Post by Sir Col on Jun 10th, 2007, 12:37pm

on 06/10/07 at 07:19:58, towr wrote:
So obviously one of us miscounted.

:P

Okay, I messed up...

As before, the distance between the centres of the circles x=1+sqrt(2)/2, so (25-1)/x~=14.06 and (20-1)/x~=11.13. Therefore we can fit 14x11 centre spans meaning 15x12 circles; confirmed by your diagram. (Very nice, towr!)

Thus there will be an array of 14x11=154 squares for which we can just guarantee to fit in a circle.

Hence adding one square to each row: 154+11=165 is an arrangement that will not allow a circle to be added.


on 06/10/07 at 10:49:00, Grimbal wrote:
So, 165 is an upper bound to the minumum number of squares that can prevent a circle to be placed in the rectangle.


::)
Title: Re: A Rectangle with Room...
Post by towr on Jun 10th, 2007, 12:44pm
I'm not entirely sure about your reasoning there. You have to squeeze the circles/squares closer together in the horizontal direction to squeeze out the bottom row of squares. So the distance between the circles will be 1.6 in the horizontal, and 1.8 in the vertical direction, not 1+1/2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2
Title: Re: A Rectangle with Room...
Post by towr on Jun 10th, 2007, 1:53pm
I think you can get about 12% more efficient plane covering when you use a somewhat hexagonal arrangement (compared to the square grid).
I'm not sure how that translates to covering the rectangle though, any gain in the middle might be lost at the edges.

The squares would be diagonally oriented, centers 3/2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 apart; and the next row would come 1/2 + 3/4 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 below that (and shifted 3/4 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 sideways)
Title: Re: A Rectangle with Room...
Post by towr on Jun 10th, 2007, 2:40pm
I think I can cover the rectangle with 156 squares, using the hexagonal configuration.. But the picture is a bit sloppy, and I don't really have time to do it properly at the moment.
Title: Re: A Rectangle with Room...
Post by towr on Jun 11th, 2007, 10:27am
Here's a picture: http://tcw2.ai.rug.nl/~towr/156_squares.pdf
(the red lines are the extended borders of the squares and the rectangle)
Title: Re: A Rectangle with Room...
Post by SMQ on Jun 13th, 2007, 11:01am
By turning towr's pattern 90 degrees it's possible to get a slightly better fit: 152 squares.

http://www.dwarfrune.com/~smq/wu/rectsquares.gif

The "hexagonal" arrangement is a provable optimum for covering the plane, and the "wasted" area in the pattern above is < 17 squares-worth, so the lower bound is definitely strictly greater than 135 squares.  However, the above arrangement just barely avoids leaving "holes" at the edges of the rectangle (all "margins" are < 1/16), so I think it will be very difficult to improve on.

I've tried several other orientations and the second-best I've come up with needs 155 squares, with the average being over 160.

--SMQ


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board