Author |
Topic: A Rectangle with Room... (Read 801 times) |
|
JP05
Guest
|
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.
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
 |
Re: A Rectangle with Room...
« Reply #1 on: Jun 7th, 2007, 12:45am » |
 Quote  Modify
|
One approach:
Add a 1/2 unit border to the squares, see that they still cannot cover all points.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Rectangle with Room...
« Reply #2 on: Jun 7th, 2007, 1:25am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: A Rectangle with Room...
« Reply #3 on: Jun 8th, 2007, 12:00am » |
Quote Modify
|
It is possible to get 154. If it is then the maximum number of 1 x 1 on an a x b rectangle is [ak] * [bk], where [] is the integer part function and k = 2 - sqrt(2).
Actually we can get 180 unit squares on that grid. In which case the maximum number is ([(a-1)k]+1) * ([(b-1)k]+1), where k = 2 - sqrt(2).
|
| « Last Edit: Jun 9th, 2007, 5:26pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Bishamon
Newbie
Gender:
Posts: 8
|
|
Re: A Rectangle with Room...
« Reply #4 on: Jun 8th, 2007, 1:16am » |
Quote Modify
|
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.
|
| « Last Edit: Jun 8th, 2007, 1:18am by Bishamon » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Rectangle with Room...
« Reply #5 on: Jun 8th, 2007, 2:59am » |
Quote Modify
|
on Jun 8th, 2007, 1:16am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Rectangle with Room...
« Reply #6 on: Jun 8th, 2007, 3:28am » |
Quote Modify
|
on Jun 8th, 2007, 1:16am, 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/2 2 x 1+1/22 for any unit circles. (A figure Sir Col already gave.) So that's already at least a lower upper bound.
|
| « Last Edit: Jun 8th, 2007, 1:24pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Bishamon
Newbie
Gender:
Posts: 8
|
|
Re: A Rectangle with Room...
« Reply #7 on: Jun 8th, 2007, 6:28am » |
Quote Modify
|
could you please how u arrived at 1 + ((0.5)/sqrt2)*(1+(0.5)*sqrt2) . (Did i get this correct?)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Rectangle with Room...
« Reply #8 on: Jun 8th, 2007, 1:34pm » |
Quote Modify
|
on Jun 8th, 2007, 6:28am, 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)*2)*(1+(0.5)*2)
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 2 + 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 2, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
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.
|
| « Last Edit: Jun 9th, 2007, 3:21am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Rectangle with Room...
« Reply #10 on: Jun 9th, 2007, 12:53pm » |
Quote Modify
|
on Jun 9th, 2007, 3:12am, 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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: A Rectangle with Room...
« Reply #11 on: Jun 9th, 2007, 5:28pm » |
Quote Modify
|
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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Rectangle with Room...
« Reply #12 on: Jun 10th, 2007, 7:19am » |
Quote Modify
|
on Jun 9th, 2007, 5:28pm, 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 2) 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
Here is a pdf with a vectorgraphics representation of the covering, to scale.
|
| « Last Edit: Jun 10th, 2007, 8:44am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A Rectangle with Room...
« Reply #14 on: Jun 10th, 2007, 10:49am » |
Quote Modify
|
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.
|
| « Last Edit: Jun 10th, 2007, 10:54am by Grimbal » |
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: A Rectangle with Room...
« Reply #15 on: Jun 10th, 2007, 12:37pm » |
Quote Modify
|
on Jun 10th, 2007, 7:19am, towr wrote:| So obviously one of us miscounted. |
|
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 Jun 10th, 2007, 10:49am, 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. |
|
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
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/22
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Rectangle with Room...
« Reply #17 on: Jun 10th, 2007, 1:53pm » |
Quote Modify
|
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 2 apart; and the next row would come 1/2 + 3/4 2 below that (and shifted 3/4 2 sideways)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Rectangle with Room...
« Reply #18 on: Jun 10th, 2007, 2:40pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A Rectangle with Room...
« Reply #20 on: Jun 13th, 2007, 11:01am » |
Quote Modify
|
By turning towr's pattern 90 degrees it's possible to get a slightly better fit: 152 squares.
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
|
|
IP Logged |
--SMQ
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove
svg_squares_and_circles.pdf