There is a space for a circle in a rectangle filled with squares
up vote
0
down vote
favorite
I placed 120 unit squares inside a $20times 25$ rectangle. Prove that it is possible to place a circle with an unit diameter (with a diameter witj length 1), such that it doesn’t have a common point with any of the squares!
I love combinatorical problems, but I couldn’t solve it. I don’t know how to start. Maybe coloring? I am sure it uses pigeonhole/principle.
combinatorics pigeonhole-principle
asked Nov 21 at 22:04
Ti Tu Lea
284
add a comment |
up vote
0
down vote
favorite
I placed 120 unit squares inside a $20times 25$ rectangle. Prove that it is possible to place a circle with an unit diameter (with a diameter witj length 1), such that it doesn’t have a common point with any of the squares!
I love combinatorical problems, but I couldn’t solve it. I don’t know how to start. Maybe coloring? I am sure it uses pigeonhole/principle.
combinatorics pigeonhole-principle
asked Nov 21 at 22:04
Ti Tu Lea
284
A circle with unit diameter is contained inside an unit square. Then a $20times 25$ rectangle could contain up to $500$ unit square then after you've added all the $120$ squares remain certainly space for another square (and then for a circle).
– P De Donato
Nov 21 at 22:11
Are the vertices of the squares required to have integer coordinates? (I suspect that it's true without this requirement, but that it will be quite a bit trickier to prove.)
– Rob Arthan
Nov 21 at 22:12
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I placed 120 unit squares inside a $20times 25$ rectangle. Prove that it is possible to place a circle with an unit diameter (with a diameter witj length 1), such that it doesn’t have a common point with any of the squares!
I love combinatorical problems, but I couldn’t solve it. I don’t know how to start. Maybe coloring? I am sure it uses pigeonhole/principle.
combinatorics pigeonhole-principle
asked Nov 21 at 22:04
Ti Tu Lea
284
I placed 120 unit squares inside a $20times 25$ rectangle. Prove that it is possible to place a circle with an unit diameter (with a diameter witj length 1), such that it doesn’t have a common point with any of the squares!
I love combinatorical problems, but I couldn’t solve it. I don’t know how to start. Maybe coloring? I am sure it uses pigeonhole/principle.
combinatorics pigeonhole-principle
combinatorics pigeonhole-principle
asked Nov 21 at 22:04
Ti Tu Lea
284
asked Nov 21 at 22:04
Ti Tu Lea
284
asked Nov 21 at 22:04
Ti Tu Lea
284
asked Nov 21 at 22:04
Ti Tu Lea
284
asked Nov 21 at 22:04
Ti Tu Lea
284
284
A circle with unit diameter is contained inside an unit square. Then a $20times 25$ rectangle could contain up to $500$ unit square then after you've added all the $120$ squares remain certainly space for another square (and then for a circle).
– P De Donato
Nov 21 at 22:11
Are the vertices of the squares required to have integer coordinates? (I suspect that it's true without this requirement, but that it will be quite a bit trickier to prove.)
– Rob Arthan
Nov 21 at 22:12
add a comment |
A circle with unit diameter is contained inside an unit square. Then a $20times 25$ rectangle could contain up to $500$ unit square then after you've added all the $120$ squares remain certainly space for another square (and then for a circle).
– P De Donato
Nov 21 at 22:11
Are the vertices of the squares required to have integer coordinates? (I suspect that it's true without this requirement, but that it will be quite a bit trickier to prove.)
– Rob Arthan
Nov 21 at 22:12
A circle with unit diameter is contained inside an unit square. Then a $20times 25$ rectangle could contain up to $500$ unit square then after you've added all the $120$ squares remain certainly space for another square (and then for a circle).
– P De Donato
Nov 21 at 22:11
A circle with unit diameter is contained inside an unit square. Then a $20times 25$ rectangle could contain up to $500$ unit square then after you've added all the $120$ squares remain certainly space for another square (and then for a circle).
– P De Donato
Nov 21 at 22:11
Are the vertices of the squares required to have integer coordinates? (I suspect that it's true without this requirement, but that it will be quite a bit trickier to prove.)
– Rob Arthan
Nov 21 at 22:12
Are the vertices of the squares required to have integer coordinates? (I suspect that it's true without this requirement, but that it will be quite a bit trickier to prove.)
– Rob Arthan
Nov 21 at 22:12
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
I think the best way to approach this is to reframe the question. Instead of trying to stop a circle from overlapping unit squares, we're going to start with the set of points in which we're "allowed" to place the center of the circle and slowly remove points. If there are any points left when we're done, we know we can place the center of the square there.
First note that the center of the circle needs to be at least 0.5 units away from the edge of the rectangle, so we're working with an area of $19*24 = 456$ square units.
Consider a single unit square and imagine a 2x2 square forcefield surrounding the unit square, but round the corners of the force field so they become quarter circles as pictured below.
If you place the center of the circle anywhere in this region, the center of the circle will be within 0.5 units from some point in the unit square, which means the circle will overlap the square. So we can't put the center of the circle in any of these points. The area of this set of points is $3+frac{pi}{4}approx3.785$ units (One unit square, four rectangles, four quarter-circles). We can surround each unit square with a set of disallowed points like this for a total area of $120 * (3+frac{pi}{3}) approx 454$ units. But the area we started with was $456$ units, so even if we are able to optimally spread out the unit squares so that no two of the forcefields overlap, there will still be a small area left over in which we can put the center of the circle.
answered Nov 22 at 0:00
WhatToDo
2516
+1 good hint....
– achille hui
Nov 22 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 at 5:59
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
I think the best way to approach this is to reframe the question. Instead of trying to stop a circle from overlapping unit squares, we're going to start with the set of points in which we're "allowed" to place the center of the circle and slowly remove points. If there are any points left when we're done, we know we can place the center of the square there.
First note that the center of the circle needs to be at least 0.5 units away from the edge of the rectangle, so we're working with an area of $19*24 = 456$ square units.
Consider a single unit square and imagine a 2x2 square forcefield surrounding the unit square, but round the corners of the force field so they become quarter circles as pictured below.
If you place the center of the circle anywhere in this region, the center of the circle will be within 0.5 units from some point in the unit square, which means the circle will overlap the square. So we can't put the center of the circle in any of these points. The area of this set of points is $3+frac{pi}{4}approx3.785$ units (One unit square, four rectangles, four quarter-circles). We can surround each unit square with a set of disallowed points like this for a total area of $120 * (3+frac{pi}{3}) approx 454$ units. But the area we started with was $456$ units, so even if we are able to optimally spread out the unit squares so that no two of the forcefields overlap, there will still be a small area left over in which we can put the center of the circle.
answered Nov 22 at 0:00
WhatToDo
2516
+1 good hint....
– achille hui
Nov 22 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 at 5:59
add a comment |
up vote
2
down vote
accepted
I think the best way to approach this is to reframe the question. Instead of trying to stop a circle from overlapping unit squares, we're going to start with the set of points in which we're "allowed" to place the center of the circle and slowly remove points. If there are any points left when we're done, we know we can place the center of the square there.
First note that the center of the circle needs to be at least 0.5 units away from the edge of the rectangle, so we're working with an area of $19*24 = 456$ square units.
Consider a single unit square and imagine a 2x2 square forcefield surrounding the unit square, but round the corners of the force field so they become quarter circles as pictured below.
If you place the center of the circle anywhere in this region, the center of the circle will be within 0.5 units from some point in the unit square, which means the circle will overlap the square. So we can't put the center of the circle in any of these points. The area of this set of points is $3+frac{pi}{4}approx3.785$ units (One unit square, four rectangles, four quarter-circles). We can surround each unit square with a set of disallowed points like this for a total area of $120 * (3+frac{pi}{3}) approx 454$ units. But the area we started with was $456$ units, so even if we are able to optimally spread out the unit squares so that no two of the forcefields overlap, there will still be a small area left over in which we can put the center of the circle.
answered Nov 22 at 0:00
WhatToDo
2516
+1 good hint....
– achille hui
Nov 22 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 at 5:59
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
I think the best way to approach this is to reframe the question. Instead of trying to stop a circle from overlapping unit squares, we're going to start with the set of points in which we're "allowed" to place the center of the circle and slowly remove points. If there are any points left when we're done, we know we can place the center of the square there.
First note that the center of the circle needs to be at least 0.5 units away from the edge of the rectangle, so we're working with an area of $19*24 = 456$ square units.
Consider a single unit square and imagine a 2x2 square forcefield surrounding the unit square, but round the corners of the force field so they become quarter circles as pictured below.
If you place the center of the circle anywhere in this region, the center of the circle will be within 0.5 units from some point in the unit square, which means the circle will overlap the square. So we can't put the center of the circle in any of these points. The area of this set of points is $3+frac{pi}{4}approx3.785$ units (One unit square, four rectangles, four quarter-circles). We can surround each unit square with a set of disallowed points like this for a total area of $120 * (3+frac{pi}{3}) approx 454$ units. But the area we started with was $456$ units, so even if we are able to optimally spread out the unit squares so that no two of the forcefields overlap, there will still be a small area left over in which we can put the center of the circle.
answered Nov 22 at 0:00
WhatToDo
2516
I think the best way to approach this is to reframe the question. Instead of trying to stop a circle from overlapping unit squares, we're going to start with the set of points in which we're "allowed" to place the center of the circle and slowly remove points. If there are any points left when we're done, we know we can place the center of the square there.
First note that the center of the circle needs to be at least 0.5 units away from the edge of the rectangle, so we're working with an area of $19*24 = 456$ square units.
Consider a single unit square and imagine a 2x2 square forcefield surrounding the unit square, but round the corners of the force field so they become quarter circles as pictured below.
If you place the center of the circle anywhere in this region, the center of the circle will be within 0.5 units from some point in the unit square, which means the circle will overlap the square. So we can't put the center of the circle in any of these points. The area of this set of points is $3+frac{pi}{4}approx3.785$ units (One unit square, four rectangles, four quarter-circles). We can surround each unit square with a set of disallowed points like this for a total area of $120 * (3+frac{pi}{3}) approx 454$ units. But the area we started with was $456$ units, so even if we are able to optimally spread out the unit squares so that no two of the forcefields overlap, there will still be a small area left over in which we can put the center of the circle.
answered Nov 22 at 0:00
WhatToDo
2516
edited Nov 22 at 14:39
answered Nov 22 at 0:00
WhatToDo
2516
answered Nov 22 at 0:00
WhatToDo
2516
answered Nov 22 at 0:00
WhatToDo
2516
2516
+1 good hint....
– achille hui
Nov 22 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 at 5:59
add a comment |
+1 good hint....
– achille hui
Nov 22 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 at 5:59
+1 good hint....
– achille hui
Nov 22 at 0:01
+1 good hint....
– achille hui
Nov 22 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 at 5:59
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 at 5:59
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3008448%2fthere-is-a-space-for-a-circle-in-a-rectangle-filled-with-squares%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
A circle with unit diameter is contained inside an unit square. Then a $20times 25$ rectangle could contain up to $500$ unit square then after you've added all the $120$ squares remain certainly space for another square (and then for a circle).
– P De Donato
Nov 21 at 22:11
Are the vertices of the squares required to have integer coordinates? (I suspect that it's true without this requirement, but that it will be quite a bit trickier to prove.)
– Rob Arthan
Nov 21 at 22:12