Several rectangles cover the unit square. Can I find a disjoint set of them whose area is at least $1/4$?
$begingroup$
I am interested in the following question:
Let a finite sequence of rectangles in $mathbb{R}^2$ be given such that
The edges of the rectangles are parallel to the coordinate axes, and
The rectangles cover the unit square, $[0,1]^2$.
Is it possible to find, among these rectangles, a collection of mutually disjoint rectangles whose combined area is at least $1/4$?
As of yet, I'm not sure if a solution exists. My friend and I have spent a while thinking about this and have gotten nowhere.
Any help is greatly appreciated.
combinatorics geometry combinatorial-geometry
asked Nov 24 '18 at 2:45
Nathaniel BNathaniel B
851616
$endgroup$
|
show 9 more comments
$begingroup$
I am interested in the following question:
Let a finite sequence of rectangles in $mathbb{R}^2$ be given such that
The edges of the rectangles are parallel to the coordinate axes, and
The rectangles cover the unit square, $[0,1]^2$.
Is it possible to find, among these rectangles, a collection of mutually disjoint rectangles whose combined area is at least $1/4$?
As of yet, I'm not sure if a solution exists. My friend and I have spent a while thinking about this and have gotten nowhere.
Any help is greatly appreciated.
combinatorics geometry combinatorial-geometry
asked Nov 24 '18 at 2:45
Nathaniel BNathaniel B
851616
$endgroup$
$begingroup$
Where'd you come across this problem? This is very nifty looking.
$endgroup$
– Steven Stadnicki
Nov 24 '18 at 2:52
3
$begingroup$
This was asked before: math.stackexchange.com/questions/2381180/…
$endgroup$
– Alon Amit
Nov 24 '18 at 3:03
1
$begingroup$
@AlonAmit - Close, but not quite: in that question, the ratio is to the total area covered by all the rectangles (thus the chosen solution, which uses overlapping rectangles covering areas of unbounded size). In this question, the ratio is to the unit square, so the solution there does not apply here.
$endgroup$
– Paul Sinclair
Nov 24 '18 at 15:23
1
$begingroup$
@snulty Without loss of generality, we can assume that the rectangle is equal to the union, since we can just replace each rectangle by its intersection with the unit square.
$endgroup$
– Misha Lavrov
Nov 28 '18 at 3:46
1
$begingroup$
@ChristianBlatter: It doesn't really matter... assume they're closed (so "cover the unit square" is as easy as possible) and that rectangles just sharing edges are considered disjoint (so "mutually disjoint" is as easy as possible), and the answer is still "no" (for any constant $c>0$, not just $1/4$).
$endgroup$
– mjqxxxx
Nov 28 '18 at 18:21
|
show 9 more comments
$begingroup$
I am interested in the following question:
Let a finite sequence of rectangles in $mathbb{R}^2$ be given such that
The edges of the rectangles are parallel to the coordinate axes, and
The rectangles cover the unit square, $[0,1]^2$.
Is it possible to find, among these rectangles, a collection of mutually disjoint rectangles whose combined area is at least $1/4$?
As of yet, I'm not sure if a solution exists. My friend and I have spent a while thinking about this and have gotten nowhere.
Any help is greatly appreciated.
combinatorics geometry combinatorial-geometry
asked Nov 24 '18 at 2:45
Nathaniel BNathaniel B
851616
$endgroup$
I am interested in the following question:
Let a finite sequence of rectangles in $mathbb{R}^2$ be given such that
The edges of the rectangles are parallel to the coordinate axes, and
The rectangles cover the unit square, $[0,1]^2$.
Is it possible to find, among these rectangles, a collection of mutually disjoint rectangles whose combined area is at least $1/4$?
As of yet, I'm not sure if a solution exists. My friend and I have spent a while thinking about this and have gotten nowhere.
Any help is greatly appreciated.
combinatorics geometry combinatorial-geometry
combinatorics geometry combinatorial-geometry
asked Nov 24 '18 at 2:45
Nathaniel BNathaniel B
851616
asked Nov 24 '18 at 2:45
Nathaniel BNathaniel B
851616
asked Nov 24 '18 at 2:45
Nathaniel BNathaniel B
851616
asked Nov 24 '18 at 2:45
Nathaniel BNathaniel B
851616
asked Nov 24 '18 at 2:45
Nathaniel BNathaniel B
851616
851616
$begingroup$
Where'd you come across this problem? This is very nifty looking.
$endgroup$
– Steven Stadnicki
Nov 24 '18 at 2:52
3
$begingroup$
This was asked before: math.stackexchange.com/questions/2381180/…
$endgroup$
– Alon Amit
Nov 24 '18 at 3:03
1
$begingroup$
@AlonAmit - Close, but not quite: in that question, the ratio is to the total area covered by all the rectangles (thus the chosen solution, which uses overlapping rectangles covering areas of unbounded size). In this question, the ratio is to the unit square, so the solution there does not apply here.
$endgroup$
– Paul Sinclair
Nov 24 '18 at 15:23
1
$begingroup$
@snulty Without loss of generality, we can assume that the rectangle is equal to the union, since we can just replace each rectangle by its intersection with the unit square.
$endgroup$
– Misha Lavrov
Nov 28 '18 at 3:46
1
$begingroup$
@ChristianBlatter: It doesn't really matter... assume they're closed (so "cover the unit square" is as easy as possible) and that rectangles just sharing edges are considered disjoint (so "mutually disjoint" is as easy as possible), and the answer is still "no" (for any constant $c>0$, not just $1/4$).
$endgroup$
– mjqxxxx
Nov 28 '18 at 18:21
|
show 9 more comments
$begingroup$
Where'd you come across this problem? This is very nifty looking.
$endgroup$
– Steven Stadnicki
Nov 24 '18 at 2:52
3
$begingroup$
This was asked before: math.stackexchange.com/questions/2381180/…
$endgroup$
– Alon Amit
Nov 24 '18 at 3:03
1
$begingroup$
@AlonAmit - Close, but not quite: in that question, the ratio is to the total area covered by all the rectangles (thus the chosen solution, which uses overlapping rectangles covering areas of unbounded size). In this question, the ratio is to the unit square, so the solution there does not apply here.
$endgroup$
– Paul Sinclair
Nov 24 '18 at 15:23
1
$begingroup$
@snulty Without loss of generality, we can assume that the rectangle is equal to the union, since we can just replace each rectangle by its intersection with the unit square.
$endgroup$
– Misha Lavrov
Nov 28 '18 at 3:46
1
$begingroup$
@ChristianBlatter: It doesn't really matter... assume they're closed (so "cover the unit square" is as easy as possible) and that rectangles just sharing edges are considered disjoint (so "mutually disjoint" is as easy as possible), and the answer is still "no" (for any constant $c>0$, not just $1/4$).
$endgroup$
– mjqxxxx
Nov 28 '18 at 18:21
$begingroup$
Where'd you come across this problem? This is very nifty looking.
$endgroup$
– Steven Stadnicki
Nov 24 '18 at 2:52
$begingroup$
Where'd you come across this problem? This is very nifty looking.
$endgroup$
– Steven Stadnicki
Nov 24 '18 at 2:52
3
3
$begingroup$
This was asked before: math.stackexchange.com/questions/2381180/…
$endgroup$
– Alon Amit
Nov 24 '18 at 3:03
$begingroup$
This was asked before: math.stackexchange.com/questions/2381180/…
$endgroup$
– Alon Amit
Nov 24 '18 at 3:03
1
1
$begingroup$
@AlonAmit - Close, but not quite: in that question, the ratio is to the total area covered by all the rectangles (thus the chosen solution, which uses overlapping rectangles covering areas of unbounded size). In this question, the ratio is to the unit square, so the solution there does not apply here.
$endgroup$
– Paul Sinclair
Nov 24 '18 at 15:23
$begingroup$
@AlonAmit - Close, but not quite: in that question, the ratio is to the total area covered by all the rectangles (thus the chosen solution, which uses overlapping rectangles covering areas of unbounded size). In this question, the ratio is to the unit square, so the solution there does not apply here.
$endgroup$
– Paul Sinclair
Nov 24 '18 at 15:23
1
1
$begingroup$
@snulty Without loss of generality, we can assume that the rectangle is equal to the union, since we can just replace each rectangle by its intersection with the unit square.
$endgroup$
– Misha Lavrov
Nov 28 '18 at 3:46
$begingroup$
@snulty Without loss of generality, we can assume that the rectangle is equal to the union, since we can just replace each rectangle by its intersection with the unit square.
$endgroup$
– Misha Lavrov
Nov 28 '18 at 3:46
1
1
$begingroup$
@ChristianBlatter: It doesn't really matter... assume they're closed (so "cover the unit square" is as easy as possible) and that rectangles just sharing edges are considered disjoint (so "mutually disjoint" is as easy as possible), and the answer is still "no" (for any constant $c>0$, not just $1/4$).
$endgroup$
– mjqxxxx
Nov 28 '18 at 18:21
$begingroup$
@ChristianBlatter: It doesn't really matter... assume they're closed (so "cover the unit square" is as easy as possible) and that rectangles just sharing edges are considered disjoint (so "mutually disjoint" is as easy as possible), and the answer is still "no" (for any constant $c>0$, not just $1/4$).
$endgroup$
– mjqxxxx
Nov 28 '18 at 18:21
|
show 9 more comments
1 Answer
1
active
oldest
votes
$begingroup$
The question linked by @AlonAmit in the comments answers exactly this question, and shows that the answer (at least with the constant $1/4$) is no. For a concrete demonstration, start with a $6times 6$ square broken into thirty-sixths:
$$
begin{matrix}
0&1&2&3&4&5\
6&7&8&9&a&b\
c&d&e&f&g&h\
i&j&k&l&m&n\
o&p&q&r&s&t\
u&v&w&x&y&z
end{matrix}
$$
Now cover each corner $2times2$ by four individual $(1+varepsilon)times (1+varepsilon)$ rectangles, such that the four rectangles in the upper left ($0,1,6,7$) are mutually overlapping, as are those in each of the other corners. And cover the remaining shape in the center (a cross) by eight individual $(3+varepsilon)times(1+varepsilon)$ rectangles ($28e$, $39f$, $cde$, $ijk$, $kqw$, $lrx$, $fgh$, and $lmn$), such that all eight include the center of the square. Any disjoint set of these rectangles includes at most four of the $(1+varepsilon)times(1+varepsilon)$ rectangles and at most one of the $(3+varepsilon)times(1+varepsilon)$ rectangles, and so has total area just over $7/36approx 19.4%$ of the full square.
answered Nov 28 '18 at 4:28
mjqxxxxmjqxxxx
31.2k24086
$endgroup$
$begingroup$
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
$endgroup$
– snulty
Nov 28 '18 at 9:37
$begingroup$
I would've thought theres arrangements where you cover 4 corners of the box, i.e. the four 2x2 squares, and the squares you've used are disjoint which would mean you've covered 16/36 of the area, since each letter represents 1/36 the area right? I must be misunderstanding something
$endgroup$
– snulty
Nov 28 '18 at 15:00
$begingroup$
@snulty: By $(1+varepsilon)times(1+varepsilon)$, I mean covering a single small square plus a little extra. There's no disjoint set of the rectangles I listed that cover a corner $2times 2$, because each corner $2times 2$ is covered by four mutually overlapping rectangles, of which you can only include one.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:25
$begingroup$
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:28
5
$begingroup$
@mjqxxxx: I find this kind of answers very helpful, so I created an SVG image (nominal-animal.net/answers/unit-square-36.svg) you can use if you want to illustrate the covering. (Consider it public domain, or CC0-1.0 licensed.) The rectangles have rounded corners to make it easier to perceive the overlappings. The small squares areas are $frac{1+epsilon}{36} approx 0.0278$ of the unit square, and the larger rectangles $frac{3+epsilon}{36} approx 0.0834$. The largest disjoint sets contain four squares and one rectangle, for a maximum area of approx $0.1945$.
$endgroup$
– Nominal Animal
Nov 29 '18 at 3:56
|
show 1 more 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%2f3011113%2fseveral-rectangles-cover-the-unit-square-can-i-find-a-disjoint-set-of-them-whos%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
$begingroup$
The question linked by @AlonAmit in the comments answers exactly this question, and shows that the answer (at least with the constant $1/4$) is no. For a concrete demonstration, start with a $6times 6$ square broken into thirty-sixths:
$$
begin{matrix}
0&1&2&3&4&5\
6&7&8&9&a&b\
c&d&e&f&g&h\
i&j&k&l&m&n\
o&p&q&r&s&t\
u&v&w&x&y&z
end{matrix}
$$
Now cover each corner $2times2$ by four individual $(1+varepsilon)times (1+varepsilon)$ rectangles, such that the four rectangles in the upper left ($0,1,6,7$) are mutually overlapping, as are those in each of the other corners. And cover the remaining shape in the center (a cross) by eight individual $(3+varepsilon)times(1+varepsilon)$ rectangles ($28e$, $39f$, $cde$, $ijk$, $kqw$, $lrx$, $fgh$, and $lmn$), such that all eight include the center of the square. Any disjoint set of these rectangles includes at most four of the $(1+varepsilon)times(1+varepsilon)$ rectangles and at most one of the $(3+varepsilon)times(1+varepsilon)$ rectangles, and so has total area just over $7/36approx 19.4%$ of the full square.
answered Nov 28 '18 at 4:28
mjqxxxxmjqxxxx
31.2k24086
$endgroup$
$begingroup$
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
$endgroup$
– snulty
Nov 28 '18 at 9:37
$begingroup$
I would've thought theres arrangements where you cover 4 corners of the box, i.e. the four 2x2 squares, and the squares you've used are disjoint which would mean you've covered 16/36 of the area, since each letter represents 1/36 the area right? I must be misunderstanding something
$endgroup$
– snulty
Nov 28 '18 at 15:00
$begingroup$
@snulty: By $(1+varepsilon)times(1+varepsilon)$, I mean covering a single small square plus a little extra. There's no disjoint set of the rectangles I listed that cover a corner $2times 2$, because each corner $2times 2$ is covered by four mutually overlapping rectangles, of which you can only include one.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:25
$begingroup$
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:28
5
$begingroup$
@mjqxxxx: I find this kind of answers very helpful, so I created an SVG image (nominal-animal.net/answers/unit-square-36.svg) you can use if you want to illustrate the covering. (Consider it public domain, or CC0-1.0 licensed.) The rectangles have rounded corners to make it easier to perceive the overlappings. The small squares areas are $frac{1+epsilon}{36} approx 0.0278$ of the unit square, and the larger rectangles $frac{3+epsilon}{36} approx 0.0834$. The largest disjoint sets contain four squares and one rectangle, for a maximum area of approx $0.1945$.
$endgroup$
– Nominal Animal
Nov 29 '18 at 3:56
|
show 1 more comment
$begingroup$
The question linked by @AlonAmit in the comments answers exactly this question, and shows that the answer (at least with the constant $1/4$) is no. For a concrete demonstration, start with a $6times 6$ square broken into thirty-sixths:
$$
begin{matrix}
0&1&2&3&4&5\
6&7&8&9&a&b\
c&d&e&f&g&h\
i&j&k&l&m&n\
o&p&q&r&s&t\
u&v&w&x&y&z
end{matrix}
$$
Now cover each corner $2times2$ by four individual $(1+varepsilon)times (1+varepsilon)$ rectangles, such that the four rectangles in the upper left ($0,1,6,7$) are mutually overlapping, as are those in each of the other corners. And cover the remaining shape in the center (a cross) by eight individual $(3+varepsilon)times(1+varepsilon)$ rectangles ($28e$, $39f$, $cde$, $ijk$, $kqw$, $lrx$, $fgh$, and $lmn$), such that all eight include the center of the square. Any disjoint set of these rectangles includes at most four of the $(1+varepsilon)times(1+varepsilon)$ rectangles and at most one of the $(3+varepsilon)times(1+varepsilon)$ rectangles, and so has total area just over $7/36approx 19.4%$ of the full square.
answered Nov 28 '18 at 4:28
mjqxxxxmjqxxxx
31.2k24086
$endgroup$
$begingroup$
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
$endgroup$
– snulty
Nov 28 '18 at 9:37
$begingroup$
I would've thought theres arrangements where you cover 4 corners of the box, i.e. the four 2x2 squares, and the squares you've used are disjoint which would mean you've covered 16/36 of the area, since each letter represents 1/36 the area right? I must be misunderstanding something
$endgroup$
– snulty
Nov 28 '18 at 15:00
$begingroup$
@snulty: By $(1+varepsilon)times(1+varepsilon)$, I mean covering a single small square plus a little extra. There's no disjoint set of the rectangles I listed that cover a corner $2times 2$, because each corner $2times 2$ is covered by four mutually overlapping rectangles, of which you can only include one.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:25
$begingroup$
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:28
5
$begingroup$
@mjqxxxx: I find this kind of answers very helpful, so I created an SVG image (nominal-animal.net/answers/unit-square-36.svg) you can use if you want to illustrate the covering. (Consider it public domain, or CC0-1.0 licensed.) The rectangles have rounded corners to make it easier to perceive the overlappings. The small squares areas are $frac{1+epsilon}{36} approx 0.0278$ of the unit square, and the larger rectangles $frac{3+epsilon}{36} approx 0.0834$. The largest disjoint sets contain four squares and one rectangle, for a maximum area of approx $0.1945$.
$endgroup$
– Nominal Animal
Nov 29 '18 at 3:56
|
show 1 more comment
$begingroup$
The question linked by @AlonAmit in the comments answers exactly this question, and shows that the answer (at least with the constant $1/4$) is no. For a concrete demonstration, start with a $6times 6$ square broken into thirty-sixths:
$$
begin{matrix}
0&1&2&3&4&5\
6&7&8&9&a&b\
c&d&e&f&g&h\
i&j&k&l&m&n\
o&p&q&r&s&t\
u&v&w&x&y&z
end{matrix}
$$
Now cover each corner $2times2$ by four individual $(1+varepsilon)times (1+varepsilon)$ rectangles, such that the four rectangles in the upper left ($0,1,6,7$) are mutually overlapping, as are those in each of the other corners. And cover the remaining shape in the center (a cross) by eight individual $(3+varepsilon)times(1+varepsilon)$ rectangles ($28e$, $39f$, $cde$, $ijk$, $kqw$, $lrx$, $fgh$, and $lmn$), such that all eight include the center of the square. Any disjoint set of these rectangles includes at most four of the $(1+varepsilon)times(1+varepsilon)$ rectangles and at most one of the $(3+varepsilon)times(1+varepsilon)$ rectangles, and so has total area just over $7/36approx 19.4%$ of the full square.
answered Nov 28 '18 at 4:28
mjqxxxxmjqxxxx
31.2k24086
$endgroup$
The question linked by @AlonAmit in the comments answers exactly this question, and shows that the answer (at least with the constant $1/4$) is no. For a concrete demonstration, start with a $6times 6$ square broken into thirty-sixths:
$$
begin{matrix}
0&1&2&3&4&5\
6&7&8&9&a&b\
c&d&e&f&g&h\
i&j&k&l&m&n\
o&p&q&r&s&t\
u&v&w&x&y&z
end{matrix}
$$
Now cover each corner $2times2$ by four individual $(1+varepsilon)times (1+varepsilon)$ rectangles, such that the four rectangles in the upper left ($0,1,6,7$) are mutually overlapping, as are those in each of the other corners. And cover the remaining shape in the center (a cross) by eight individual $(3+varepsilon)times(1+varepsilon)$ rectangles ($28e$, $39f$, $cde$, $ijk$, $kqw$, $lrx$, $fgh$, and $lmn$), such that all eight include the center of the square. Any disjoint set of these rectangles includes at most four of the $(1+varepsilon)times(1+varepsilon)$ rectangles and at most one of the $(3+varepsilon)times(1+varepsilon)$ rectangles, and so has total area just over $7/36approx 19.4%$ of the full square.
answered Nov 28 '18 at 4:28
mjqxxxxmjqxxxx
31.2k24086
edited Nov 28 '18 at 15:26
answered Nov 28 '18 at 4:28
mjqxxxxmjqxxxx
31.2k24086
answered Nov 28 '18 at 4:28
mjqxxxxmjqxxxx
31.2k24086
answered Nov 28 '18 at 4:28
mjqxxxxmjqxxxx
31.2k24086
31.2k24086
$begingroup$
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
$endgroup$
– snulty
Nov 28 '18 at 9:37
$begingroup$
I would've thought theres arrangements where you cover 4 corners of the box, i.e. the four 2x2 squares, and the squares you've used are disjoint which would mean you've covered 16/36 of the area, since each letter represents 1/36 the area right? I must be misunderstanding something
$endgroup$
– snulty
Nov 28 '18 at 15:00
$begingroup$
@snulty: By $(1+varepsilon)times(1+varepsilon)$, I mean covering a single small square plus a little extra. There's no disjoint set of the rectangles I listed that cover a corner $2times 2$, because each corner $2times 2$ is covered by four mutually overlapping rectangles, of which you can only include one.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:25
$begingroup$
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:28
5
$begingroup$
@mjqxxxx: I find this kind of answers very helpful, so I created an SVG image (nominal-animal.net/answers/unit-square-36.svg) you can use if you want to illustrate the covering. (Consider it public domain, or CC0-1.0 licensed.) The rectangles have rounded corners to make it easier to perceive the overlappings. The small squares areas are $frac{1+epsilon}{36} approx 0.0278$ of the unit square, and the larger rectangles $frac{3+epsilon}{36} approx 0.0834$. The largest disjoint sets contain four squares and one rectangle, for a maximum area of approx $0.1945$.
$endgroup$
– Nominal Animal
Nov 29 '18 at 3:56
|
show 1 more comment
$begingroup$
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
$endgroup$
– snulty
Nov 28 '18 at 9:37
$begingroup$
I would've thought theres arrangements where you cover 4 corners of the box, i.e. the four 2x2 squares, and the squares you've used are disjoint which would mean you've covered 16/36 of the area, since each letter represents 1/36 the area right? I must be misunderstanding something
$endgroup$
– snulty
Nov 28 '18 at 15:00
$begingroup$
@snulty: By $(1+varepsilon)times(1+varepsilon)$, I mean covering a single small square plus a little extra. There's no disjoint set of the rectangles I listed that cover a corner $2times 2$, because each corner $2times 2$ is covered by four mutually overlapping rectangles, of which you can only include one.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:25
$begingroup$
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:28
5
$begingroup$
@mjqxxxx: I find this kind of answers very helpful, so I created an SVG image (nominal-animal.net/answers/unit-square-36.svg) you can use if you want to illustrate the covering. (Consider it public domain, or CC0-1.0 licensed.) The rectangles have rounded corners to make it easier to perceive the overlappings. The small squares areas are $frac{1+epsilon}{36} approx 0.0278$ of the unit square, and the larger rectangles $frac{3+epsilon}{36} approx 0.0834$. The largest disjoint sets contain four squares and one rectangle, for a maximum area of approx $0.1945$.
$endgroup$
– Nominal Animal
Nov 29 '18 at 3:56
$begingroup$
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
$endgroup$
– snulty
Nov 28 '18 at 9:37
$begingroup$
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
$endgroup$
– snulty
Nov 28 '18 at 9:37
$begingroup$
I would've thought theres arrangements where you cover 4 corners of the box, i.e. the four 2x2 squares, and the squares you've used are disjoint which would mean you've covered 16/36 of the area, since each letter represents 1/36 the area right? I must be misunderstanding something
$endgroup$
– snulty
Nov 28 '18 at 15:00
$begingroup$
I would've thought theres arrangements where you cover 4 corners of the box, i.e. the four 2x2 squares, and the squares you've used are disjoint which would mean you've covered 16/36 of the area, since each letter represents 1/36 the area right? I must be misunderstanding something
$endgroup$
– snulty
Nov 28 '18 at 15:00
$begingroup$
@snulty: By $(1+varepsilon)times(1+varepsilon)$, I mean covering a single small square plus a little extra. There's no disjoint set of the rectangles I listed that cover a corner $2times 2$, because each corner $2times 2$ is covered by four mutually overlapping rectangles, of which you can only include one.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:25
$begingroup$
@snulty: By $(1+varepsilon)times(1+varepsilon)$, I mean covering a single small square plus a little extra. There's no disjoint set of the rectangles I listed that cover a corner $2times 2$, because each corner $2times 2$ is covered by four mutually overlapping rectangles, of which you can only include one.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:25
$begingroup$
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:28
$begingroup$
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
$endgroup$
– mjqxxxx
Nov 28 '18 at 15:28
5
5
$begingroup$
@mjqxxxx: I find this kind of answers very helpful, so I created an SVG image (nominal-animal.net/answers/unit-square-36.svg) you can use if you want to illustrate the covering. (Consider it public domain, or CC0-1.0 licensed.) The rectangles have rounded corners to make it easier to perceive the overlappings. The small squares areas are $frac{1+epsilon}{36} approx 0.0278$ of the unit square, and the larger rectangles $frac{3+epsilon}{36} approx 0.0834$. The largest disjoint sets contain four squares and one rectangle, for a maximum area of approx $0.1945$.
$endgroup$
– Nominal Animal
Nov 29 '18 at 3:56
$begingroup$
@mjqxxxx: I find this kind of answers very helpful, so I created an SVG image (nominal-animal.net/answers/unit-square-36.svg) you can use if you want to illustrate the covering. (Consider it public domain, or CC0-1.0 licensed.) The rectangles have rounded corners to make it easier to perceive the overlappings. The small squares areas are $frac{1+epsilon}{36} approx 0.0278$ of the unit square, and the larger rectangles $frac{3+epsilon}{36} approx 0.0834$. The largest disjoint sets contain four squares and one rectangle, for a maximum area of approx $0.1945$.
$endgroup$
– Nominal Animal
Nov 29 '18 at 3:56
|
show 1 more 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.
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%2f3011113%2fseveral-rectangles-cover-the-unit-square-can-i-find-a-disjoint-set-of-them-whos%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
$begingroup$
Where'd you come across this problem? This is very nifty looking.
$endgroup$
– Steven Stadnicki
Nov 24 '18 at 2:52
3
$begingroup$
This was asked before: math.stackexchange.com/questions/2381180/…
$endgroup$
– Alon Amit
Nov 24 '18 at 3:03
1
$begingroup$
@AlonAmit - Close, but not quite: in that question, the ratio is to the total area covered by all the rectangles (thus the chosen solution, which uses overlapping rectangles covering areas of unbounded size). In this question, the ratio is to the unit square, so the solution there does not apply here.
$endgroup$
– Paul Sinclair
Nov 24 '18 at 15:23
1
$begingroup$
@snulty Without loss of generality, we can assume that the rectangle is equal to the union, since we can just replace each rectangle by its intersection with the unit square.
$endgroup$
– Misha Lavrov
Nov 28 '18 at 3:46
1
$begingroup$
@ChristianBlatter: It doesn't really matter... assume they're closed (so "cover the unit square" is as easy as possible) and that rectangles just sharing edges are considered disjoint (so "mutually disjoint" is as easy as possible), and the answer is still "no" (for any constant $c>0$, not just $1/4$).
$endgroup$
– mjqxxxx
Nov 28 '18 at 18:21