$2^n times 2^n$ chessboard with one square removed - Is the tiling unique?
$begingroup$
It is well-known that a $2^n times 2^n$ chessboard with an arbitrary square removed is tilable by an L-shaped tromino (piece composed of three squares). The standard proof is by induction, and is constructive (gives an algorithm for producing such a tiling).
My question is: For a given chessboard with a fixed square removed, is this tiling unique?
tiling
asked Dec 11 '18 at 16:31
Samuel LiSamuel Li
504311
$endgroup$
add a comment |
$begingroup$
It is well-known that a $2^n times 2^n$ chessboard with an arbitrary square removed is tilable by an L-shaped tromino (piece composed of three squares). The standard proof is by induction, and is constructive (gives an algorithm for producing such a tiling).
My question is: For a given chessboard with a fixed square removed, is this tiling unique?
tiling
asked Dec 11 '18 at 16:31
Samuel LiSamuel Li
504311
$endgroup$
add a comment |
$begingroup$
It is well-known that a $2^n times 2^n$ chessboard with an arbitrary square removed is tilable by an L-shaped tromino (piece composed of three squares). The standard proof is by induction, and is constructive (gives an algorithm for producing such a tiling).
My question is: For a given chessboard with a fixed square removed, is this tiling unique?
tiling
asked Dec 11 '18 at 16:31
Samuel LiSamuel Li
504311
$endgroup$
It is well-known that a $2^n times 2^n$ chessboard with an arbitrary square removed is tilable by an L-shaped tromino (piece composed of three squares). The standard proof is by induction, and is constructive (gives an algorithm for producing such a tiling).
My question is: For a given chessboard with a fixed square removed, is this tiling unique?
tiling
tiling
asked Dec 11 '18 at 16:31
Samuel LiSamuel Li
504311
asked Dec 11 '18 at 16:31
Samuel LiSamuel Li
504311
asked Dec 11 '18 at 16:31
Samuel LiSamuel Li
504311
asked Dec 11 '18 at 16:31
Samuel LiSamuel Li
504311
asked Dec 11 '18 at 16:31
Samuel LiSamuel Li
504311
504311
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
No, it is not unique at least starting from $n=3,$ so an $8 times 8$ board. Note that two L trominoes can combine to make a $2 times 3$ rectangle. This rectangle can have the pieces placed two ways. Now let the removed square be a corner. Put one L next to it to make a $2 times 2$ square. You can tile the rest of the board with five $2 times 6$ rectangles as shown below. Each $2 times 6$ can be tiled in four ways, so this gives $1024$ ways to tile the square. I believe the $n=2$ case is unique but have not done a careful search to prove it.
answered Dec 11 '18 at 16:47
Ross MillikanRoss Millikan
297k23198371
$endgroup$
add a comment |
$begingroup$
Here are two explicit tiling of the 8x8 board. I got the second board just by playing around with the tiling.
answered Dec 11 '18 at 16:55
DubsDubs
55926
$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%2f3035471%2f2n-times-2n-chessboard-with-one-square-removed-is-the-tiling-unique%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
No, it is not unique at least starting from $n=3,$ so an $8 times 8$ board. Note that two L trominoes can combine to make a $2 times 3$ rectangle. This rectangle can have the pieces placed two ways. Now let the removed square be a corner. Put one L next to it to make a $2 times 2$ square. You can tile the rest of the board with five $2 times 6$ rectangles as shown below. Each $2 times 6$ can be tiled in four ways, so this gives $1024$ ways to tile the square. I believe the $n=2$ case is unique but have not done a careful search to prove it.
answered Dec 11 '18 at 16:47
Ross MillikanRoss Millikan
297k23198371
$endgroup$
add a comment |
$begingroup$
No, it is not unique at least starting from $n=3,$ so an $8 times 8$ board. Note that two L trominoes can combine to make a $2 times 3$ rectangle. This rectangle can have the pieces placed two ways. Now let the removed square be a corner. Put one L next to it to make a $2 times 2$ square. You can tile the rest of the board with five $2 times 6$ rectangles as shown below. Each $2 times 6$ can be tiled in four ways, so this gives $1024$ ways to tile the square. I believe the $n=2$ case is unique but have not done a careful search to prove it.
answered Dec 11 '18 at 16:47
Ross MillikanRoss Millikan
297k23198371
$endgroup$
add a comment |
$begingroup$
No, it is not unique at least starting from $n=3,$ so an $8 times 8$ board. Note that two L trominoes can combine to make a $2 times 3$ rectangle. This rectangle can have the pieces placed two ways. Now let the removed square be a corner. Put one L next to it to make a $2 times 2$ square. You can tile the rest of the board with five $2 times 6$ rectangles as shown below. Each $2 times 6$ can be tiled in four ways, so this gives $1024$ ways to tile the square. I believe the $n=2$ case is unique but have not done a careful search to prove it.
answered Dec 11 '18 at 16:47
Ross MillikanRoss Millikan
297k23198371
$endgroup$
No, it is not unique at least starting from $n=3,$ so an $8 times 8$ board. Note that two L trominoes can combine to make a $2 times 3$ rectangle. This rectangle can have the pieces placed two ways. Now let the removed square be a corner. Put one L next to it to make a $2 times 2$ square. You can tile the rest of the board with five $2 times 6$ rectangles as shown below. Each $2 times 6$ can be tiled in four ways, so this gives $1024$ ways to tile the square. I believe the $n=2$ case is unique but have not done a careful search to prove it.
answered Dec 11 '18 at 16:47
Ross MillikanRoss Millikan
297k23198371
answered Dec 11 '18 at 16:47
Ross MillikanRoss Millikan
297k23198371
answered Dec 11 '18 at 16:47
Ross MillikanRoss Millikan
297k23198371
answered Dec 11 '18 at 16:47
Ross MillikanRoss Millikan
297k23198371
297k23198371
add a comment |
add a comment |
$begingroup$
Here are two explicit tiling of the 8x8 board. I got the second board just by playing around with the tiling.
answered Dec 11 '18 at 16:55
DubsDubs
55926
$endgroup$
add a comment |
$begingroup$
Here are two explicit tiling of the 8x8 board. I got the second board just by playing around with the tiling.
answered Dec 11 '18 at 16:55
DubsDubs
55926
$endgroup$
add a comment |
$begingroup$
Here are two explicit tiling of the 8x8 board. I got the second board just by playing around with the tiling.
answered Dec 11 '18 at 16:55
DubsDubs
55926
$endgroup$
Here are two explicit tiling of the 8x8 board. I got the second board just by playing around with the tiling.
answered Dec 11 '18 at 16:55
DubsDubs
55926
answered Dec 11 '18 at 16:55
DubsDubs
55926
answered Dec 11 '18 at 16:55
DubsDubs
55926
answered Dec 11 '18 at 16:55
DubsDubs
55926
55926
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%2f3035471%2f2n-times-2n-chessboard-with-one-square-removed-is-the-tiling-unique%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
