Mixing
Minimum number of rectangles to cover diagonal-free grid
$begingroup$
I'm trying to figure out the minimum number of rectangles required to cover an $n times n$ grid, minus the diagonal. What this is means is the following: Suppose we have an $n times n$ grid, with the diagonal missing. What is the minimum umber of rectangles I need that are contained within the grid such that the union of the rectangles covers the entire grid?
I think the answer should be $log_2 n$. Attainment is easy, there are two $n^2/4$ squares (by which I mean two squares with area $n^2/4$), four $n^2/16$ squares, 8 $n^2/64$ squares, and so on. Summing this (and assuming $n = 2^m$) you get
$$
sum_{k=1}^{m = log_2 n} 2^k cdot n^2/4^k = sum_{k=1}^m n^2 2^{-k} = n^2(1 - 1/n) = n^2 - n.
$$
But I don't see a clean way to argue that this is the best you can do.
combinatorics discrete-optimization rectangles
asked Jan 27 at 3:28
Drew BradyDrew Brady
721315
$endgroup$
add a comment |
$begingroup$
I'm trying to figure out the minimum number of rectangles required to cover an $n times n$ grid, minus the diagonal. What this is means is the following: Suppose we have an $n times n$ grid, with the diagonal missing. What is the minimum umber of rectangles I need that are contained within the grid such that the union of the rectangles covers the entire grid?
I think the answer should be $log_2 n$. Attainment is easy, there are two $n^2/4$ squares (by which I mean two squares with area $n^2/4$), four $n^2/16$ squares, 8 $n^2/64$ squares, and so on. Summing this (and assuming $n = 2^m$) you get
$$
sum_{k=1}^{m = log_2 n} 2^k cdot n^2/4^k = sum_{k=1}^m n^2 2^{-k} = n^2(1 - 1/n) = n^2 - n.
$$
But I don't see a clean way to argue that this is the best you can do.
combinatorics discrete-optimization rectangles
asked Jan 27 at 3:28
Drew BradyDrew Brady
721315
$endgroup$
$begingroup$
log base 2 of n ?? I tried it for n=8 and I get 14 (7 on each side of the diagonal). But log base 2 of n for n=8 gives 3 ???
$endgroup$
– Vinzent
Jan 27 at 4:00
$begingroup$
"there are two n^2/4 squares (by which I mean two squares with area n^2/4), four n^2/16 squares, 8 n^2/64 squares, and so on" This seems to only hold for even values of n.. in all the cases I've tested so far it seems that 2*(n-1) is the best solution.
$endgroup$
– Vinzent
Jan 27 at 4:12
$begingroup$
Can those rectangles overlap
$endgroup$
– Maria Mazur
Jan 27 at 7:39
add a comment |
$begingroup$
I'm trying to figure out the minimum number of rectangles required to cover an $n times n$ grid, minus the diagonal. What this is means is the following: Suppose we have an $n times n$ grid, with the diagonal missing. What is the minimum umber of rectangles I need that are contained within the grid such that the union of the rectangles covers the entire grid?
I think the answer should be $log_2 n$. Attainment is easy, there are two $n^2/4$ squares (by which I mean two squares with area $n^2/4$), four $n^2/16$ squares, 8 $n^2/64$ squares, and so on. Summing this (and assuming $n = 2^m$) you get
$$
sum_{k=1}^{m = log_2 n} 2^k cdot n^2/4^k = sum_{k=1}^m n^2 2^{-k} = n^2(1 - 1/n) = n^2 - n.
$$
But I don't see a clean way to argue that this is the best you can do.
combinatorics discrete-optimization rectangles
asked Jan 27 at 3:28
Drew BradyDrew Brady
721315
$endgroup$
I'm trying to figure out the minimum number of rectangles required to cover an $n times n$ grid, minus the diagonal. What this is means is the following: Suppose we have an $n times n$ grid, with the diagonal missing. What is the minimum umber of rectangles I need that are contained within the grid such that the union of the rectangles covers the entire grid?
I think the answer should be $log_2 n$. Attainment is easy, there are two $n^2/4$ squares (by which I mean two squares with area $n^2/4$), four $n^2/16$ squares, 8 $n^2/64$ squares, and so on. Summing this (and assuming $n = 2^m$) you get
$$
sum_{k=1}^{m = log_2 n} 2^k cdot n^2/4^k = sum_{k=1}^m n^2 2^{-k} = n^2(1 - 1/n) = n^2 - n.
$$
But I don't see a clean way to argue that this is the best you can do.
combinatorics discrete-optimization rectangles
combinatorics discrete-optimization rectangles
asked Jan 27 at 3:28
Drew BradyDrew Brady
721315
asked Jan 27 at 3:28
Drew BradyDrew Brady
721315
asked Jan 27 at 3:28
Drew BradyDrew Brady
721315
asked Jan 27 at 3:28
Drew BradyDrew Brady
721315
asked Jan 27 at 3:28
Drew BradyDrew Brady
721315
721315
$begingroup$
log base 2 of n ?? I tried it for n=8 and I get 14 (7 on each side of the diagonal). But log base 2 of n for n=8 gives 3 ???
$endgroup$
– Vinzent
Jan 27 at 4:00
$begingroup$
"there are two n^2/4 squares (by which I mean two squares with area n^2/4), four n^2/16 squares, 8 n^2/64 squares, and so on" This seems to only hold for even values of n.. in all the cases I've tested so far it seems that 2*(n-1) is the best solution.
$endgroup$
– Vinzent
Jan 27 at 4:12
$begingroup$
Can those rectangles overlap
$endgroup$
– Maria Mazur
Jan 27 at 7:39
add a comment |
$begingroup$
log base 2 of n ?? I tried it for n=8 and I get 14 (7 on each side of the diagonal). But log base 2 of n for n=8 gives 3 ???
$endgroup$
– Vinzent
Jan 27 at 4:00
$begingroup$
"there are two n^2/4 squares (by which I mean two squares with area n^2/4), four n^2/16 squares, 8 n^2/64 squares, and so on" This seems to only hold for even values of n.. in all the cases I've tested so far it seems that 2*(n-1) is the best solution.
$endgroup$
– Vinzent
Jan 27 at 4:12
$begingroup$
Can those rectangles overlap
$endgroup$
– Maria Mazur
Jan 27 at 7:39
$begingroup$
log base 2 of n ?? I tried it for n=8 and I get 14 (7 on each side of the diagonal). But log base 2 of n for n=8 gives 3 ???
$endgroup$
– Vinzent
Jan 27 at 4:00
$begingroup$
log base 2 of n ?? I tried it for n=8 and I get 14 (7 on each side of the diagonal). But log base 2 of n for n=8 gives 3 ???
$endgroup$
– Vinzent
Jan 27 at 4:00
$begingroup$
"there are two n^2/4 squares (by which I mean two squares with area n^2/4), four n^2/16 squares, 8 n^2/64 squares, and so on" This seems to only hold for even values of n.. in all the cases I've tested so far it seems that 2*(n-1) is the best solution.
$endgroup$
– Vinzent
Jan 27 at 4:12
$begingroup$
"there are two n^2/4 squares (by which I mean two squares with area n^2/4), four n^2/16 squares, 8 n^2/64 squares, and so on" This seems to only hold for even values of n.. in all the cases I've tested so far it seems that 2*(n-1) is the best solution.
$endgroup$
– Vinzent
Jan 27 at 4:12
$begingroup$
Can those rectangles overlap
$endgroup$
– Maria Mazur
Jan 27 at 7:39
$begingroup$
Can those rectangles overlap
$endgroup$
– Maria Mazur
Jan 27 at 7:39
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Suppose that each square in the grid has coordinates $i,j$ representing its row and column. Take a look at squares: (1,2), (2,3), (3,4), ..., ($n$-1, $n$) above the diagonal and (2,1), (3,2), ..., ($n$, $n-1$) under the diagonal. There is no rectangle covering any two squares picked from this set at the same time.
So you need at least $2(n-1)$ rectangles just to cover all squares from this set. Fortunately, you can cover the whole board with the same number of rectangles (a set of horizontal rectangles of height 1 will do the job).
So the minimum number of rectangles is really $2(n-1)$.
answered Jan 27 at 7:10
OldboyOldboy
8,91111138
$endgroup$
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%2f3089101%2fminimum-number-of-rectangles-to-cover-diagonal-free-grid%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$
Suppose that each square in the grid has coordinates $i,j$ representing its row and column. Take a look at squares: (1,2), (2,3), (3,4), ..., ($n$-1, $n$) above the diagonal and (2,1), (3,2), ..., ($n$, $n-1$) under the diagonal. There is no rectangle covering any two squares picked from this set at the same time.
So you need at least $2(n-1)$ rectangles just to cover all squares from this set. Fortunately, you can cover the whole board with the same number of rectangles (a set of horizontal rectangles of height 1 will do the job).
So the minimum number of rectangles is really $2(n-1)$.
answered Jan 27 at 7:10
OldboyOldboy
8,91111138
$endgroup$
add a comment |
$begingroup$
Suppose that each square in the grid has coordinates $i,j$ representing its row and column. Take a look at squares: (1,2), (2,3), (3,4), ..., ($n$-1, $n$) above the diagonal and (2,1), (3,2), ..., ($n$, $n-1$) under the diagonal. There is no rectangle covering any two squares picked from this set at the same time.
So you need at least $2(n-1)$ rectangles just to cover all squares from this set. Fortunately, you can cover the whole board with the same number of rectangles (a set of horizontal rectangles of height 1 will do the job).
So the minimum number of rectangles is really $2(n-1)$.
answered Jan 27 at 7:10
OldboyOldboy
8,91111138
$endgroup$
add a comment |
$begingroup$
Suppose that each square in the grid has coordinates $i,j$ representing its row and column. Take a look at squares: (1,2), (2,3), (3,4), ..., ($n$-1, $n$) above the diagonal and (2,1), (3,2), ..., ($n$, $n-1$) under the diagonal. There is no rectangle covering any two squares picked from this set at the same time.
So you need at least $2(n-1)$ rectangles just to cover all squares from this set. Fortunately, you can cover the whole board with the same number of rectangles (a set of horizontal rectangles of height 1 will do the job).
So the minimum number of rectangles is really $2(n-1)$.
answered Jan 27 at 7:10
OldboyOldboy
8,91111138
$endgroup$
Suppose that each square in the grid has coordinates $i,j$ representing its row and column. Take a look at squares: (1,2), (2,3), (3,4), ..., ($n$-1, $n$) above the diagonal and (2,1), (3,2), ..., ($n$, $n-1$) under the diagonal. There is no rectangle covering any two squares picked from this set at the same time.
So you need at least $2(n-1)$ rectangles just to cover all squares from this set. Fortunately, you can cover the whole board with the same number of rectangles (a set of horizontal rectangles of height 1 will do the job).
So the minimum number of rectangles is really $2(n-1)$.
answered Jan 27 at 7:10
OldboyOldboy
8,91111138
edited Jan 27 at 7:24
answered Jan 27 at 7:10
OldboyOldboy
8,91111138
answered Jan 27 at 7:10
OldboyOldboy
8,91111138
answered Jan 27 at 7:10
OldboyOldboy
8,91111138
8,91111138
add a comment |
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.
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%2f3089101%2fminimum-number-of-rectangles-to-cover-diagonal-free-grid%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$
log base 2 of n ?? I tried it for n=8 and I get 14 (7 on each side of the diagonal). But log base 2 of n for n=8 gives 3 ???
$endgroup$
– Vinzent
Jan 27 at 4:00
$begingroup$
"there are two n^2/4 squares (by which I mean two squares with area n^2/4), four n^2/16 squares, 8 n^2/64 squares, and so on" This seems to only hold for even values of n.. in all the cases I've tested so far it seems that 2*(n-1) is the best solution.
$endgroup$
– Vinzent
Jan 27 at 4:12
$begingroup$
Can those rectangles overlap
$endgroup$
– Maria Mazur
Jan 27 at 7:39