Several rectangles cover the unit square. Can I find a disjoint set of them whose area is at least $1/4$?
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 at 2:45
Nathaniel B
786516
|
show 9 more comments
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 at 2:45
Nathaniel B
786516
Where'd you come across this problem? This is very nifty looking.
– Steven Stadnicki
Nov 24 at 2:52
3
This was asked before: math.stackexchange.com/questions/2381180/…
– Alon Amit
Nov 24 at 3:03
1
@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.
– Paul Sinclair
Nov 24 at 15:23
1
@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.
– Misha Lavrov
Nov 28 at 3:46
1
@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$).
– mjqxxxx
Nov 28 at 18:21
|
show 9 more comments
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 at 2:45
Nathaniel B
786516
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 at 2:45
Nathaniel B
786516
asked Nov 24 at 2:45
Nathaniel B
786516
asked Nov 24 at 2:45
Nathaniel B
786516
asked Nov 24 at 2:45
Nathaniel B
786516
asked Nov 24 at 2:45
Nathaniel B
786516
786516
Where'd you come across this problem? This is very nifty looking.
– Steven Stadnicki
Nov 24 at 2:52
3
This was asked before: math.stackexchange.com/questions/2381180/…
– Alon Amit
Nov 24 at 3:03
1
@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.
– Paul Sinclair
Nov 24 at 15:23
1
@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.
– Misha Lavrov
Nov 28 at 3:46
1
@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$).
– mjqxxxx
Nov 28 at 18:21
|
show 9 more comments
Where'd you come across this problem? This is very nifty looking.
– Steven Stadnicki
Nov 24 at 2:52
3
This was asked before: math.stackexchange.com/questions/2381180/…
– Alon Amit
Nov 24 at 3:03
1
@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.
– Paul Sinclair
Nov 24 at 15:23
1
@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.
– Misha Lavrov
Nov 28 at 3:46
1
@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$).
– mjqxxxx
Nov 28 at 18:21
Where'd you come across this problem? This is very nifty looking.
– Steven Stadnicki
Nov 24 at 2:52
Where'd you come across this problem? This is very nifty looking.
– Steven Stadnicki
Nov 24 at 2:52
3
3
This was asked before: math.stackexchange.com/questions/2381180/…
– Alon Amit
Nov 24 at 3:03
This was asked before: math.stackexchange.com/questions/2381180/…
– Alon Amit
Nov 24 at 3:03
1
1
@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.
– Paul Sinclair
Nov 24 at 15:23
@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.
– Paul Sinclair
Nov 24 at 15:23
1
1
@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.
– Misha Lavrov
Nov 28 at 3:46
@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.
– Misha Lavrov
Nov 28 at 3:46
1
1
@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$).
– mjqxxxx
Nov 28 at 18:21
@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$).
– mjqxxxx
Nov 28 at 18:21
|
show 9 more comments
1 Answer
1
active
oldest
votes
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 at 4:28
mjqxxxx
31k23985
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
– snulty
Nov 28 at 9:37
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
– snulty
Nov 28 at 15:00
@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.
– mjqxxxx
Nov 28 at 15:25
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
– mjqxxxx
Nov 28 at 15:28
5
@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$.
– Nominal Animal
Nov 29 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
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 at 4:28
mjqxxxx
31k23985
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
– snulty
Nov 28 at 9:37
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
– snulty
Nov 28 at 15:00
@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.
– mjqxxxx
Nov 28 at 15:25
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
– mjqxxxx
Nov 28 at 15:28
5
@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$.
– Nominal Animal
Nov 29 at 3:56
|
show 1 more comment
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 at 4:28
mjqxxxx
31k23985
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
– snulty
Nov 28 at 9:37
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
– snulty
Nov 28 at 15:00
@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.
– mjqxxxx
Nov 28 at 15:25
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
– mjqxxxx
Nov 28 at 15:28
5
@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$.
– Nominal Animal
Nov 29 at 3:56
|
show 1 more comment
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 at 4:28
mjqxxxx
31k23985
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 at 4:28
mjqxxxx
31k23985
edited Nov 28 at 15:26
answered Nov 28 at 4:28
mjqxxxx
31k23985
answered Nov 28 at 4:28
mjqxxxx
31k23985
answered Nov 28 at 4:28
mjqxxxx
31k23985
31k23985
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
– snulty
Nov 28 at 9:37
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
– snulty
Nov 28 at 15:00
@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.
– mjqxxxx
Nov 28 at 15:25
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
– mjqxxxx
Nov 28 at 15:28
5
@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$.
– Nominal Animal
Nov 29 at 3:56
|
show 1 more comment
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
– snulty
Nov 28 at 9:37
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
– snulty
Nov 28 at 15:00
@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.
– mjqxxxx
Nov 28 at 15:25
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
– mjqxxxx
Nov 28 at 15:28
5
@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$.
– Nominal Animal
Nov 29 at 3:56
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
– snulty
Nov 28 at 9:37
Does a $(1+epsilon)times (1+epsilon)$ rectangle have area $1+2epsilon +epsilon^2$? Which is a big square?
– snulty
Nov 28 at 9:37
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
– snulty
Nov 28 at 15:00
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
– snulty
Nov 28 at 15:00
@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.
– mjqxxxx
Nov 28 at 15:25
@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.
– mjqxxxx
Nov 28 at 15:25
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
– mjqxxxx
Nov 28 at 15:28
@DavidC.Ullrich: I changed it to say $6times 6$ from the outset.
– mjqxxxx
Nov 28 at 15:28
5
5
@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$.
– Nominal Animal
Nov 29 at 3:56
@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$.
– Nominal Animal
Nov 29 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.
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%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
Where'd you come across this problem? This is very nifty looking.
– Steven Stadnicki
Nov 24 at 2:52
3
This was asked before: math.stackexchange.com/questions/2381180/…
– Alon Amit
Nov 24 at 3:03
1
@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.
– Paul Sinclair
Nov 24 at 15:23
1
@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.
– Misha Lavrov
Nov 28 at 3:46
1
@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$).
– mjqxxxx
Nov 28 at 18:21