Mixing
There is a space for a circle in a rectangle filled with squares
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 '18 at 22:04
Ti Tu LeaTi Tu Lea
264
add a comment |
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 '18 at 22:04
Ti Tu LeaTi Tu Lea
264
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 '18 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 '18 at 22:12
add a comment |
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 '18 at 22:04
Ti Tu LeaTi Tu Lea
264
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 '18 at 22:04
Ti Tu LeaTi Tu Lea
264
asked Nov 21 '18 at 22:04
Ti Tu LeaTi Tu Lea
264
asked Nov 21 '18 at 22:04
Ti Tu LeaTi Tu Lea
264
asked Nov 21 '18 at 22:04
Ti Tu LeaTi Tu Lea
264
asked Nov 21 '18 at 22:04
Ti Tu LeaTi Tu Lea
264
264
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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 at 22:12
add a comment |
1 Answer
1
active
oldest
votes
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 '18 at 0:00
WhatToDoWhatToDo
25116
+1 good hint....
– achille hui
Nov 22 '18 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 '18 at 5:59
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
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 '18 at 0:00
WhatToDoWhatToDo
25116
+1 good hint....
– achille hui
Nov 22 '18 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 '18 at 5:59
add a comment |
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 '18 at 0:00
WhatToDoWhatToDo
25116
+1 good hint....
– achille hui
Nov 22 '18 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 '18 at 5:59
add a comment |
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 '18 at 0:00
WhatToDoWhatToDo
25116
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 '18 at 0:00
WhatToDoWhatToDo
25116
edited Nov 22 '18 at 14:39
answered Nov 22 '18 at 0:00
WhatToDoWhatToDo
25116
answered Nov 22 '18 at 0:00
WhatToDoWhatToDo
25116
answered Nov 22 '18 at 0:00
WhatToDoWhatToDo
25116
25116
+1 good hint....
– achille hui
Nov 22 '18 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 '18 at 5:59
add a comment |
+1 good hint....
– achille hui
Nov 22 '18 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 '18 at 5:59
+1 good hint....
– achille hui
Nov 22 '18 at 0:01
+1 good hint....
– achille hui
Nov 22 '18 at 0:01
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 '18 at 5:59
I couldn’t finish your solution... Can you please post the full solution? Thanks
– Ti Tu Lea
Nov 22 '18 at 5:59
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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 '18 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 '18 at 22:12