Partially tiling a square with parallelograms
$begingroup$
I found the following puzzle on reddit, and am struggling to find the solution:
You have an $ntimes n$ square, and a supply of parallelogram tiles with side lengths $1$ and $sqrt{2}$ and angle $45$°. What is the largest number of non-overlapping tiles you can place in the square? Assume that the tiles must be placed so their vertices have integer coordinates.
It seems like the answer is $n(n-1)$, using $n$ rows of $(n-1)$ tiles.
I am stuck proving this is optimal. I think the following idea might be helpful. Divide the square into an $ntimes n$ array of square cells, and partition these cells into groups so that whenever a tile touches two cells, those two cells are in the same group. The groups will be snaking paths resembling the example below. At the end of each path are two uncovered triangles. Therefore, we need only show the $ntimes n$ grid cannot be partitioned into fewer than $n$ such paths.
X X X X
X X
X
X X
X X
combinatorics geometry puzzle tiling
edited Dec 19 '18 at 20:58
Jam
4,98221431
asked Dec 19 '18 at 20:55
zeta zerozeta zero
1105
$endgroup$
add a comment |
$begingroup$
I found the following puzzle on reddit, and am struggling to find the solution:
You have an $ntimes n$ square, and a supply of parallelogram tiles with side lengths $1$ and $sqrt{2}$ and angle $45$°. What is the largest number of non-overlapping tiles you can place in the square? Assume that the tiles must be placed so their vertices have integer coordinates.
It seems like the answer is $n(n-1)$, using $n$ rows of $(n-1)$ tiles.
I am stuck proving this is optimal. I think the following idea might be helpful. Divide the square into an $ntimes n$ array of square cells, and partition these cells into groups so that whenever a tile touches two cells, those two cells are in the same group. The groups will be snaking paths resembling the example below. At the end of each path are two uncovered triangles. Therefore, we need only show the $ntimes n$ grid cannot be partitioned into fewer than $n$ such paths.
X X X X
X X
X
X X
X X
combinatorics geometry puzzle tiling
edited Dec 19 '18 at 20:58
Jam
4,98221431
asked Dec 19 '18 at 20:55
zeta zerozeta zero
1105
$endgroup$
add a comment |
$begingroup$
I found the following puzzle on reddit, and am struggling to find the solution:
You have an $ntimes n$ square, and a supply of parallelogram tiles with side lengths $1$ and $sqrt{2}$ and angle $45$°. What is the largest number of non-overlapping tiles you can place in the square? Assume that the tiles must be placed so their vertices have integer coordinates.
It seems like the answer is $n(n-1)$, using $n$ rows of $(n-1)$ tiles.
I am stuck proving this is optimal. I think the following idea might be helpful. Divide the square into an $ntimes n$ array of square cells, and partition these cells into groups so that whenever a tile touches two cells, those two cells are in the same group. The groups will be snaking paths resembling the example below. At the end of each path are two uncovered triangles. Therefore, we need only show the $ntimes n$ grid cannot be partitioned into fewer than $n$ such paths.
X X X X
X X
X
X X
X X
combinatorics geometry puzzle tiling
edited Dec 19 '18 at 20:58
Jam
4,98221431
asked Dec 19 '18 at 20:55
zeta zerozeta zero
1105
$endgroup$
I found the following puzzle on reddit, and am struggling to find the solution:
You have an $ntimes n$ square, and a supply of parallelogram tiles with side lengths $1$ and $sqrt{2}$ and angle $45$°. What is the largest number of non-overlapping tiles you can place in the square? Assume that the tiles must be placed so their vertices have integer coordinates.
It seems like the answer is $n(n-1)$, using $n$ rows of $(n-1)$ tiles.
I am stuck proving this is optimal. I think the following idea might be helpful. Divide the square into an $ntimes n$ array of square cells, and partition these cells into groups so that whenever a tile touches two cells, those two cells are in the same group. The groups will be snaking paths resembling the example below. At the end of each path are two uncovered triangles. Therefore, we need only show the $ntimes n$ grid cannot be partitioned into fewer than $n$ such paths.
X X X X
X X
X
X X
X X
combinatorics geometry puzzle tiling
combinatorics geometry puzzle tiling
edited Dec 19 '18 at 20:58
Jam
4,98221431
asked Dec 19 '18 at 20:55
zeta zerozeta zero
1105
edited Dec 19 '18 at 20:58
Jam
4,98221431
asked Dec 19 '18 at 20:55
zeta zerozeta zero
1105
edited Dec 19 '18 at 20:58
Jam
4,98221431
edited Dec 19 '18 at 20:58
Jam
4,98221431
edited Dec 19 '18 at 20:58
Jam
4,98221431
4,98221431
asked Dec 19 '18 at 20:55
zeta zerozeta zero
1105
asked Dec 19 '18 at 20:55
zeta zerozeta zero
1105
asked Dec 19 '18 at 20:55
zeta zerozeta zero
1105
1105
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Assume the top left corner is filled without any gaps. The only way to do this is shown below. In fact, the solution you've given is equivalent to filling the top right corner - this can be shown with a reflection. I've constructed each parallelogram from 2 right triangles.
We could then tile each parallelogram on the outer "shell" without leaving any gaps, as in the following figure. Then either the tiling continues until it reaches a corner, as in the bottom left, and we have 1 missing triangle. Or at some point the tiling reverses and another corner (the top right) is filled out, in which case, we would have 2 missing triangles in the top row but get one back in the next row. NB: we could have the tiling reverse and not fill out the top right corner but this would lose us 3 triangles of area. The crux of this is that tiling a shell loses us at least 2 triangles (1 unit) of space. Alternatively, if the top left corner of a shell weren't filled, it would lose us at least 1.5 units of space.
So if the same is true for each subsequent shell, we'd have $(n-1)+1$ units of lost space, counting over $n-1$ shells and an extra unit in the bottom right. Then our total filled area is at most $n(n-1)$.
answered Dec 20 '18 at 1:39
JamJam
4,98221431
$endgroup$
$begingroup$
It's worth noting that the problem becomes quite a bit trickier if the shapes points aren't confined to lying on integers points.
$endgroup$
– Jam
Dec 20 '18 at 1:43
$begingroup$
PS. Your solution to the problem would appear to break the rule that each shell has at least 1 unit of empty space but we can circumvent this by counting the parts of parallelograms that overlap out of their shells. imgur.com/a/MoXMUkp
$endgroup$
– Jam
Dec 20 '18 at 1:58
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%2f3046867%2fpartially-tiling-a-square-with-parallelograms%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$
Assume the top left corner is filled without any gaps. The only way to do this is shown below. In fact, the solution you've given is equivalent to filling the top right corner - this can be shown with a reflection. I've constructed each parallelogram from 2 right triangles.
We could then tile each parallelogram on the outer "shell" without leaving any gaps, as in the following figure. Then either the tiling continues until it reaches a corner, as in the bottom left, and we have 1 missing triangle. Or at some point the tiling reverses and another corner (the top right) is filled out, in which case, we would have 2 missing triangles in the top row but get one back in the next row. NB: we could have the tiling reverse and not fill out the top right corner but this would lose us 3 triangles of area. The crux of this is that tiling a shell loses us at least 2 triangles (1 unit) of space. Alternatively, if the top left corner of a shell weren't filled, it would lose us at least 1.5 units of space.
So if the same is true for each subsequent shell, we'd have $(n-1)+1$ units of lost space, counting over $n-1$ shells and an extra unit in the bottom right. Then our total filled area is at most $n(n-1)$.
answered Dec 20 '18 at 1:39
JamJam
4,98221431
$endgroup$
$begingroup$
It's worth noting that the problem becomes quite a bit trickier if the shapes points aren't confined to lying on integers points.
$endgroup$
– Jam
Dec 20 '18 at 1:43
$begingroup$
PS. Your solution to the problem would appear to break the rule that each shell has at least 1 unit of empty space but we can circumvent this by counting the parts of parallelograms that overlap out of their shells. imgur.com/a/MoXMUkp
$endgroup$
– Jam
Dec 20 '18 at 1:58
add a comment |
$begingroup$
Assume the top left corner is filled without any gaps. The only way to do this is shown below. In fact, the solution you've given is equivalent to filling the top right corner - this can be shown with a reflection. I've constructed each parallelogram from 2 right triangles.
We could then tile each parallelogram on the outer "shell" without leaving any gaps, as in the following figure. Then either the tiling continues until it reaches a corner, as in the bottom left, and we have 1 missing triangle. Or at some point the tiling reverses and another corner (the top right) is filled out, in which case, we would have 2 missing triangles in the top row but get one back in the next row. NB: we could have the tiling reverse and not fill out the top right corner but this would lose us 3 triangles of area. The crux of this is that tiling a shell loses us at least 2 triangles (1 unit) of space. Alternatively, if the top left corner of a shell weren't filled, it would lose us at least 1.5 units of space.
So if the same is true for each subsequent shell, we'd have $(n-1)+1$ units of lost space, counting over $n-1$ shells and an extra unit in the bottom right. Then our total filled area is at most $n(n-1)$.
answered Dec 20 '18 at 1:39
JamJam
4,98221431
$endgroup$
$begingroup$
It's worth noting that the problem becomes quite a bit trickier if the shapes points aren't confined to lying on integers points.
$endgroup$
– Jam
Dec 20 '18 at 1:43
$begingroup$
PS. Your solution to the problem would appear to break the rule that each shell has at least 1 unit of empty space but we can circumvent this by counting the parts of parallelograms that overlap out of their shells. imgur.com/a/MoXMUkp
$endgroup$
– Jam
Dec 20 '18 at 1:58
add a comment |
$begingroup$
Assume the top left corner is filled without any gaps. The only way to do this is shown below. In fact, the solution you've given is equivalent to filling the top right corner - this can be shown with a reflection. I've constructed each parallelogram from 2 right triangles.
We could then tile each parallelogram on the outer "shell" without leaving any gaps, as in the following figure. Then either the tiling continues until it reaches a corner, as in the bottom left, and we have 1 missing triangle. Or at some point the tiling reverses and another corner (the top right) is filled out, in which case, we would have 2 missing triangles in the top row but get one back in the next row. NB: we could have the tiling reverse and not fill out the top right corner but this would lose us 3 triangles of area. The crux of this is that tiling a shell loses us at least 2 triangles (1 unit) of space. Alternatively, if the top left corner of a shell weren't filled, it would lose us at least 1.5 units of space.
So if the same is true for each subsequent shell, we'd have $(n-1)+1$ units of lost space, counting over $n-1$ shells and an extra unit in the bottom right. Then our total filled area is at most $n(n-1)$.
answered Dec 20 '18 at 1:39
JamJam
4,98221431
$endgroup$
Assume the top left corner is filled without any gaps. The only way to do this is shown below. In fact, the solution you've given is equivalent to filling the top right corner - this can be shown with a reflection. I've constructed each parallelogram from 2 right triangles.
We could then tile each parallelogram on the outer "shell" without leaving any gaps, as in the following figure. Then either the tiling continues until it reaches a corner, as in the bottom left, and we have 1 missing triangle. Or at some point the tiling reverses and another corner (the top right) is filled out, in which case, we would have 2 missing triangles in the top row but get one back in the next row. NB: we could have the tiling reverse and not fill out the top right corner but this would lose us 3 triangles of area. The crux of this is that tiling a shell loses us at least 2 triangles (1 unit) of space. Alternatively, if the top left corner of a shell weren't filled, it would lose us at least 1.5 units of space.
So if the same is true for each subsequent shell, we'd have $(n-1)+1$ units of lost space, counting over $n-1$ shells and an extra unit in the bottom right. Then our total filled area is at most $n(n-1)$.
answered Dec 20 '18 at 1:39
JamJam
4,98221431
answered Dec 20 '18 at 1:39
JamJam
4,98221431
answered Dec 20 '18 at 1:39
JamJam
4,98221431
answered Dec 20 '18 at 1:39
JamJam
4,98221431
4,98221431
$begingroup$
It's worth noting that the problem becomes quite a bit trickier if the shapes points aren't confined to lying on integers points.
$endgroup$
– Jam
Dec 20 '18 at 1:43
$begingroup$
PS. Your solution to the problem would appear to break the rule that each shell has at least 1 unit of empty space but we can circumvent this by counting the parts of parallelograms that overlap out of their shells. imgur.com/a/MoXMUkp
$endgroup$
– Jam
Dec 20 '18 at 1:58
add a comment |
$begingroup$
It's worth noting that the problem becomes quite a bit trickier if the shapes points aren't confined to lying on integers points.
$endgroup$
– Jam
Dec 20 '18 at 1:43
$begingroup$
PS. Your solution to the problem would appear to break the rule that each shell has at least 1 unit of empty space but we can circumvent this by counting the parts of parallelograms that overlap out of their shells. imgur.com/a/MoXMUkp
$endgroup$
– Jam
Dec 20 '18 at 1:58
$begingroup$
It's worth noting that the problem becomes quite a bit trickier if the shapes points aren't confined to lying on integers points.
$endgroup$
– Jam
Dec 20 '18 at 1:43
$begingroup$
It's worth noting that the problem becomes quite a bit trickier if the shapes points aren't confined to lying on integers points.
$endgroup$
– Jam
Dec 20 '18 at 1:43
$begingroup$
PS. Your solution to the problem would appear to break the rule that each shell has at least 1 unit of empty space but we can circumvent this by counting the parts of parallelograms that overlap out of their shells. imgur.com/a/MoXMUkp
$endgroup$
– Jam
Dec 20 '18 at 1:58
$begingroup$
PS. Your solution to the problem would appear to break the rule that each shell has at least 1 unit of empty space but we can circumvent this by counting the parts of parallelograms that overlap out of their shells. imgur.com/a/MoXMUkp
$endgroup$
– Jam
Dec 20 '18 at 1:58
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%2f3046867%2fpartially-tiling-a-square-with-parallelograms%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
