Proof a $2^n$ by $2^n$ board can be filled using L shaped trominoes and 1 monomino
Multi tool use
Suppose we have an $2^ntimes 2^n$ board. Prove you can use any rotation of L shaped trominoes and a monomino to fill the board completely.
You can mix different rotations in the same tililng.
combinatorics tiling
|
show 1 more comment
Suppose we have an $2^ntimes 2^n$ board. Prove you can use any rotation of L shaped trominoes and a monomino to fill the board completely.
You can mix different rotations in the same tililng.
combinatorics tiling
What exactly are your "L"-shapes? Half the border of a $4times 3$ rectangle? Or which dimensions?
– AlexR
Aug 6 '13 at 17:22
3
Are you perhaps trying to show that a $2^ntimes 2^n$ board can't be filled by trominoes and one monomino? It's totally obvious that trominoes can't fill an $8times 8$ board because 3 does not divide 64; on the other hand, they can fill a $6times 6$ board quite easily. For the $2^ntimes 2^n$ case, see mutilated chessboard problem.
– MJD
Aug 6 '13 at 17:28
3
@alexr "L-shaped tromino" is a clear and unambiguous piece of jargon in combinatorial geometry and is easy to look up on the Internet.
– MJD
Aug 6 '13 at 17:29
My mistake; the mutilated chessboard problem is something else.
– MJD
Aug 6 '13 at 17:42
2
You might enjoy trying to cover a $9times 9$ board with 27 trominoes. I found it surprisingly tricky.
– MJD
Aug 6 '13 at 18:27
|
show 1 more comment
Suppose we have an $2^ntimes 2^n$ board. Prove you can use any rotation of L shaped trominoes and a monomino to fill the board completely.
You can mix different rotations in the same tililng.
combinatorics tiling
Suppose we have an $2^ntimes 2^n$ board. Prove you can use any rotation of L shaped trominoes and a monomino to fill the board completely.
You can mix different rotations in the same tililng.
combinatorics tiling
combinatorics tiling
edited Dec 11 '16 at 8:47
Rohan
27.7k42444
27.7k42444
asked Aug 6 '13 at 17:15
Jorge Fernández
75k1189191
75k1189191
What exactly are your "L"-shapes? Half the border of a $4times 3$ rectangle? Or which dimensions?
– AlexR
Aug 6 '13 at 17:22
3
Are you perhaps trying to show that a $2^ntimes 2^n$ board can't be filled by trominoes and one monomino? It's totally obvious that trominoes can't fill an $8times 8$ board because 3 does not divide 64; on the other hand, they can fill a $6times 6$ board quite easily. For the $2^ntimes 2^n$ case, see mutilated chessboard problem.
– MJD
Aug 6 '13 at 17:28
3
@alexr "L-shaped tromino" is a clear and unambiguous piece of jargon in combinatorial geometry and is easy to look up on the Internet.
– MJD
Aug 6 '13 at 17:29
My mistake; the mutilated chessboard problem is something else.
– MJD
Aug 6 '13 at 17:42
2
You might enjoy trying to cover a $9times 9$ board with 27 trominoes. I found it surprisingly tricky.
– MJD
Aug 6 '13 at 18:27
|
show 1 more comment
What exactly are your "L"-shapes? Half the border of a $4times 3$ rectangle? Or which dimensions?
– AlexR
Aug 6 '13 at 17:22
3
Are you perhaps trying to show that a $2^ntimes 2^n$ board can't be filled by trominoes and one monomino? It's totally obvious that trominoes can't fill an $8times 8$ board because 3 does not divide 64; on the other hand, they can fill a $6times 6$ board quite easily. For the $2^ntimes 2^n$ case, see mutilated chessboard problem.
– MJD
Aug 6 '13 at 17:28
3
@alexr "L-shaped tromino" is a clear and unambiguous piece of jargon in combinatorial geometry and is easy to look up on the Internet.
– MJD
Aug 6 '13 at 17:29
My mistake; the mutilated chessboard problem is something else.
– MJD
Aug 6 '13 at 17:42
2
You might enjoy trying to cover a $9times 9$ board with 27 trominoes. I found it surprisingly tricky.
– MJD
Aug 6 '13 at 18:27
What exactly are your "L"-shapes? Half the border of a $4times 3$ rectangle? Or which dimensions?
– AlexR
Aug 6 '13 at 17:22
What exactly are your "L"-shapes? Half the border of a $4times 3$ rectangle? Or which dimensions?
– AlexR
Aug 6 '13 at 17:22
3
3
Are you perhaps trying to show that a $2^ntimes 2^n$ board can't be filled by trominoes and one monomino? It's totally obvious that trominoes can't fill an $8times 8$ board because 3 does not divide 64; on the other hand, they can fill a $6times 6$ board quite easily. For the $2^ntimes 2^n$ case, see mutilated chessboard problem.
– MJD
Aug 6 '13 at 17:28
Are you perhaps trying to show that a $2^ntimes 2^n$ board can't be filled by trominoes and one monomino? It's totally obvious that trominoes can't fill an $8times 8$ board because 3 does not divide 64; on the other hand, they can fill a $6times 6$ board quite easily. For the $2^ntimes 2^n$ case, see mutilated chessboard problem.
– MJD
Aug 6 '13 at 17:28
3
3
@alexr "L-shaped tromino" is a clear and unambiguous piece of jargon in combinatorial geometry and is easy to look up on the Internet.
– MJD
Aug 6 '13 at 17:29
@alexr "L-shaped tromino" is a clear and unambiguous piece of jargon in combinatorial geometry and is easy to look up on the Internet.
– MJD
Aug 6 '13 at 17:29
My mistake; the mutilated chessboard problem is something else.
– MJD
Aug 6 '13 at 17:42
My mistake; the mutilated chessboard problem is something else.
– MJD
Aug 6 '13 at 17:42
2
2
You might enjoy trying to cover a $9times 9$ board with 27 trominoes. I found it surprisingly tricky.
– MJD
Aug 6 '13 at 18:27
You might enjoy trying to cover a $9times 9$ board with 27 trominoes. I found it surprisingly tricky.
– MJD
Aug 6 '13 at 18:27
|
show 1 more comment
3 Answers
3
active
oldest
votes
This is an old chestnut of combinatorial geometry. The proof is a fairly simple induction. We show that the $2^ntimes 2^n$ board can be covered by trominoes except for one square.
If $n=1$, the solution is trivial.
Otherwise, assume that we can cover a $2^{n-1}times 2^{n-1}$ board with trominoes except for one chosen square.
Divide the $2^ntimes 2^n$ board into four $2^{n-1}times 2^{n-1}$ square quadrants. One quadrant contains the square we want to leave uncovered by trominoes, and by induction we can cover this quadrant, except for the one square, with trominoes.
For the remaining three quadrants, cover each of these except for one of its corners with trominoes. Rotate the three quadrants so that their uncovered corners lie together at the center of the board. These three remaining squares can then be covered with one more tromino.
I first saw this in Polyominoes by Solomon W. Golomb. it appears on page 5 of the revised edition, Princeton University Press, 1994.
Note that this proof actually shows that a $2^n$ by $2^n$ board can be covered with $L$-shaped trominoes and a monomino, no matter where the monomino is placed.
– user133281
Aug 29 '14 at 7:22
Thanks. That is why I referred to the extra square as a "chosen" square. You can choose it to be any square you like.
– MJD
Aug 29 '14 at 13:14
add a comment |
Another example and some proof.
On some special case of putting monomino in special place, $(2m-1)×(2m-1)$ without multiple of 3 are possible. If a monomino is black, since $(6m-1)^2=3*4m(3m-1)+1$, L blocks is a multiple of 4. Then it's contradiction, so white - black=2. Therefore when $(6m-1)^2$, we can't put a monomino in a place we like.
If $(6m)^2$, although L blocks is obviously odd, since $(6m^2-3)+1≠6m^2$, they can't make square. If $(6m-3)^2$, since $(6m-3)^2≠3M+1$, they can't make square.
add a comment |
Solution: Let $P(n)$ be the proposition that every $2^n times2^n$ checkerboard with one square removed can be tiled using right triominoes. We can use mathematical induction to prove that $P(n)$ is true for all positive integers $n$.
BASIS STEP: $P(1)$ is true, because each of the four $2 times 2$ checkerboards with one square removed can be tiled using one right triomino.
INDUCTIVE STEP: The inductive hypothesis is the assumption that $P(k)$ is true for the positive integer $k$; that is, it is the assumption that every $2^k times 2^k$ checkerboard with one square removed can be tiled using right triominoes.
It must be shown that under the assumption of the inductive hypothesis, $P(k+1)$ must also be true; that is, any $2^{k+1} times 2^(k+1)$ checkerboard with one square removed can be tiled using right triominoes. To see this, consider a $2k+1 times2k+1$ checkerboard with one square removed. Split this checkerboard into four checkerboards of size $2^ktimes2^k$, by dividing it in half in both directions. This is illustrated in Figure 6(??). No square has been removed from three of these four checkerboards. The fourth $2^ktimes2^k$ checkerboard has one square removed, so we now use the inductive hypothesis to conclude that it can be covered by right triominoes. Now temporarily remove the square from each of the other three $2^k times 2^k$ checkerboards that has the center of the original, larger checkerboard as one of its corners. By the inductive hypothesis, each of these three $2^k times2^k$ checkerboards with a square removed can be tiled by right triominoes. Furthermore, the three squares that were temporarily removed can be covered by one right triomino. Hence, the entire $2^{k+1} times 2^{k+1}$ checkerboard can be tiled with right triominoes. We have completed the basis step and the inductive step.
Therefore, by mathematical induction $P(n)$ is true for all positive integers $n$. This shows that we can tile every $2^n times 2^n$ checkerboard, where $n$ is a positive integer, with one square removed, using right triominoes.
You have added nothing new to the already existing answers.
– José Carlos Santos
Dec 7 at 22:24
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%2f461252%2fproof-a-2n-by-2n-board-can-be-filled-using-l-shaped-trominoes-and-1-monomi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
This is an old chestnut of combinatorial geometry. The proof is a fairly simple induction. We show that the $2^ntimes 2^n$ board can be covered by trominoes except for one square.
If $n=1$, the solution is trivial.
Otherwise, assume that we can cover a $2^{n-1}times 2^{n-1}$ board with trominoes except for one chosen square.
Divide the $2^ntimes 2^n$ board into four $2^{n-1}times 2^{n-1}$ square quadrants. One quadrant contains the square we want to leave uncovered by trominoes, and by induction we can cover this quadrant, except for the one square, with trominoes.
For the remaining three quadrants, cover each of these except for one of its corners with trominoes. Rotate the three quadrants so that their uncovered corners lie together at the center of the board. These three remaining squares can then be covered with one more tromino.
I first saw this in Polyominoes by Solomon W. Golomb. it appears on page 5 of the revised edition, Princeton University Press, 1994.
Note that this proof actually shows that a $2^n$ by $2^n$ board can be covered with $L$-shaped trominoes and a monomino, no matter where the monomino is placed.
– user133281
Aug 29 '14 at 7:22
Thanks. That is why I referred to the extra square as a "chosen" square. You can choose it to be any square you like.
– MJD
Aug 29 '14 at 13:14
add a comment |
This is an old chestnut of combinatorial geometry. The proof is a fairly simple induction. We show that the $2^ntimes 2^n$ board can be covered by trominoes except for one square.
If $n=1$, the solution is trivial.
Otherwise, assume that we can cover a $2^{n-1}times 2^{n-1}$ board with trominoes except for one chosen square.
Divide the $2^ntimes 2^n$ board into four $2^{n-1}times 2^{n-1}$ square quadrants. One quadrant contains the square we want to leave uncovered by trominoes, and by induction we can cover this quadrant, except for the one square, with trominoes.
For the remaining three quadrants, cover each of these except for one of its corners with trominoes. Rotate the three quadrants so that their uncovered corners lie together at the center of the board. These three remaining squares can then be covered with one more tromino.
I first saw this in Polyominoes by Solomon W. Golomb. it appears on page 5 of the revised edition, Princeton University Press, 1994.
Note that this proof actually shows that a $2^n$ by $2^n$ board can be covered with $L$-shaped trominoes and a monomino, no matter where the monomino is placed.
– user133281
Aug 29 '14 at 7:22
Thanks. That is why I referred to the extra square as a "chosen" square. You can choose it to be any square you like.
– MJD
Aug 29 '14 at 13:14
add a comment |
This is an old chestnut of combinatorial geometry. The proof is a fairly simple induction. We show that the $2^ntimes 2^n$ board can be covered by trominoes except for one square.
If $n=1$, the solution is trivial.
Otherwise, assume that we can cover a $2^{n-1}times 2^{n-1}$ board with trominoes except for one chosen square.
Divide the $2^ntimes 2^n$ board into four $2^{n-1}times 2^{n-1}$ square quadrants. One quadrant contains the square we want to leave uncovered by trominoes, and by induction we can cover this quadrant, except for the one square, with trominoes.
For the remaining three quadrants, cover each of these except for one of its corners with trominoes. Rotate the three quadrants so that their uncovered corners lie together at the center of the board. These three remaining squares can then be covered with one more tromino.
I first saw this in Polyominoes by Solomon W. Golomb. it appears on page 5 of the revised edition, Princeton University Press, 1994.
This is an old chestnut of combinatorial geometry. The proof is a fairly simple induction. We show that the $2^ntimes 2^n$ board can be covered by trominoes except for one square.
If $n=1$, the solution is trivial.
Otherwise, assume that we can cover a $2^{n-1}times 2^{n-1}$ board with trominoes except for one chosen square.
Divide the $2^ntimes 2^n$ board into four $2^{n-1}times 2^{n-1}$ square quadrants. One quadrant contains the square we want to leave uncovered by trominoes, and by induction we can cover this quadrant, except for the one square, with trominoes.
For the remaining three quadrants, cover each of these except for one of its corners with trominoes. Rotate the three quadrants so that their uncovered corners lie together at the center of the board. These three remaining squares can then be covered with one more tromino.
I first saw this in Polyominoes by Solomon W. Golomb. it appears on page 5 of the revised edition, Princeton University Press, 1994.
edited Aug 6 '13 at 18:30
answered Aug 6 '13 at 17:42
MJD
46.9k28207392
46.9k28207392
Note that this proof actually shows that a $2^n$ by $2^n$ board can be covered with $L$-shaped trominoes and a monomino, no matter where the monomino is placed.
– user133281
Aug 29 '14 at 7:22
Thanks. That is why I referred to the extra square as a "chosen" square. You can choose it to be any square you like.
– MJD
Aug 29 '14 at 13:14
add a comment |
Note that this proof actually shows that a $2^n$ by $2^n$ board can be covered with $L$-shaped trominoes and a monomino, no matter where the monomino is placed.
– user133281
Aug 29 '14 at 7:22
Thanks. That is why I referred to the extra square as a "chosen" square. You can choose it to be any square you like.
– MJD
Aug 29 '14 at 13:14
Note that this proof actually shows that a $2^n$ by $2^n$ board can be covered with $L$-shaped trominoes and a monomino, no matter where the monomino is placed.
– user133281
Aug 29 '14 at 7:22
Note that this proof actually shows that a $2^n$ by $2^n$ board can be covered with $L$-shaped trominoes and a monomino, no matter where the monomino is placed.
– user133281
Aug 29 '14 at 7:22
Thanks. That is why I referred to the extra square as a "chosen" square. You can choose it to be any square you like.
– MJD
Aug 29 '14 at 13:14
Thanks. That is why I referred to the extra square as a "chosen" square. You can choose it to be any square you like.
– MJD
Aug 29 '14 at 13:14
add a comment |
Another example and some proof.
On some special case of putting monomino in special place, $(2m-1)×(2m-1)$ without multiple of 3 are possible. If a monomino is black, since $(6m-1)^2=3*4m(3m-1)+1$, L blocks is a multiple of 4. Then it's contradiction, so white - black=2. Therefore when $(6m-1)^2$, we can't put a monomino in a place we like.
If $(6m)^2$, although L blocks is obviously odd, since $(6m^2-3)+1≠6m^2$, they can't make square. If $(6m-3)^2$, since $(6m-3)^2≠3M+1$, they can't make square.
add a comment |
Another example and some proof.
On some special case of putting monomino in special place, $(2m-1)×(2m-1)$ without multiple of 3 are possible. If a monomino is black, since $(6m-1)^2=3*4m(3m-1)+1$, L blocks is a multiple of 4. Then it's contradiction, so white - black=2. Therefore when $(6m-1)^2$, we can't put a monomino in a place we like.
If $(6m)^2$, although L blocks is obviously odd, since $(6m^2-3)+1≠6m^2$, they can't make square. If $(6m-3)^2$, since $(6m-3)^2≠3M+1$, they can't make square.
add a comment |
Another example and some proof.
On some special case of putting monomino in special place, $(2m-1)×(2m-1)$ without multiple of 3 are possible. If a monomino is black, since $(6m-1)^2=3*4m(3m-1)+1$, L blocks is a multiple of 4. Then it's contradiction, so white - black=2. Therefore when $(6m-1)^2$, we can't put a monomino in a place we like.
If $(6m)^2$, although L blocks is obviously odd, since $(6m^2-3)+1≠6m^2$, they can't make square. If $(6m-3)^2$, since $(6m-3)^2≠3M+1$, they can't make square.
Another example and some proof.
On some special case of putting monomino in special place, $(2m-1)×(2m-1)$ without multiple of 3 are possible. If a monomino is black, since $(6m-1)^2=3*4m(3m-1)+1$, L blocks is a multiple of 4. Then it's contradiction, so white - black=2. Therefore when $(6m-1)^2$, we can't put a monomino in a place we like.
If $(6m)^2$, although L blocks is obviously odd, since $(6m^2-3)+1≠6m^2$, they can't make square. If $(6m-3)^2$, since $(6m-3)^2≠3M+1$, they can't make square.
answered Mar 13 '17 at 8:28
Takahiro Waki
2,073620
2,073620
add a comment |
add a comment |
Solution: Let $P(n)$ be the proposition that every $2^n times2^n$ checkerboard with one square removed can be tiled using right triominoes. We can use mathematical induction to prove that $P(n)$ is true for all positive integers $n$.
BASIS STEP: $P(1)$ is true, because each of the four $2 times 2$ checkerboards with one square removed can be tiled using one right triomino.
INDUCTIVE STEP: The inductive hypothesis is the assumption that $P(k)$ is true for the positive integer $k$; that is, it is the assumption that every $2^k times 2^k$ checkerboard with one square removed can be tiled using right triominoes.
It must be shown that under the assumption of the inductive hypothesis, $P(k+1)$ must also be true; that is, any $2^{k+1} times 2^(k+1)$ checkerboard with one square removed can be tiled using right triominoes. To see this, consider a $2k+1 times2k+1$ checkerboard with one square removed. Split this checkerboard into four checkerboards of size $2^ktimes2^k$, by dividing it in half in both directions. This is illustrated in Figure 6(??). No square has been removed from three of these four checkerboards. The fourth $2^ktimes2^k$ checkerboard has one square removed, so we now use the inductive hypothesis to conclude that it can be covered by right triominoes. Now temporarily remove the square from each of the other three $2^k times 2^k$ checkerboards that has the center of the original, larger checkerboard as one of its corners. By the inductive hypothesis, each of these three $2^k times2^k$ checkerboards with a square removed can be tiled by right triominoes. Furthermore, the three squares that were temporarily removed can be covered by one right triomino. Hence, the entire $2^{k+1} times 2^{k+1}$ checkerboard can be tiled with right triominoes. We have completed the basis step and the inductive step.
Therefore, by mathematical induction $P(n)$ is true for all positive integers $n$. This shows that we can tile every $2^n times 2^n$ checkerboard, where $n$ is a positive integer, with one square removed, using right triominoes.
You have added nothing new to the already existing answers.
– José Carlos Santos
Dec 7 at 22:24
add a comment |
Solution: Let $P(n)$ be the proposition that every $2^n times2^n$ checkerboard with one square removed can be tiled using right triominoes. We can use mathematical induction to prove that $P(n)$ is true for all positive integers $n$.
BASIS STEP: $P(1)$ is true, because each of the four $2 times 2$ checkerboards with one square removed can be tiled using one right triomino.
INDUCTIVE STEP: The inductive hypothesis is the assumption that $P(k)$ is true for the positive integer $k$; that is, it is the assumption that every $2^k times 2^k$ checkerboard with one square removed can be tiled using right triominoes.
It must be shown that under the assumption of the inductive hypothesis, $P(k+1)$ must also be true; that is, any $2^{k+1} times 2^(k+1)$ checkerboard with one square removed can be tiled using right triominoes. To see this, consider a $2k+1 times2k+1$ checkerboard with one square removed. Split this checkerboard into four checkerboards of size $2^ktimes2^k$, by dividing it in half in both directions. This is illustrated in Figure 6(??). No square has been removed from three of these four checkerboards. The fourth $2^ktimes2^k$ checkerboard has one square removed, so we now use the inductive hypothesis to conclude that it can be covered by right triominoes. Now temporarily remove the square from each of the other three $2^k times 2^k$ checkerboards that has the center of the original, larger checkerboard as one of its corners. By the inductive hypothesis, each of these three $2^k times2^k$ checkerboards with a square removed can be tiled by right triominoes. Furthermore, the three squares that were temporarily removed can be covered by one right triomino. Hence, the entire $2^{k+1} times 2^{k+1}$ checkerboard can be tiled with right triominoes. We have completed the basis step and the inductive step.
Therefore, by mathematical induction $P(n)$ is true for all positive integers $n$. This shows that we can tile every $2^n times 2^n$ checkerboard, where $n$ is a positive integer, with one square removed, using right triominoes.
You have added nothing new to the already existing answers.
– José Carlos Santos
Dec 7 at 22:24
add a comment |
Solution: Let $P(n)$ be the proposition that every $2^n times2^n$ checkerboard with one square removed can be tiled using right triominoes. We can use mathematical induction to prove that $P(n)$ is true for all positive integers $n$.
BASIS STEP: $P(1)$ is true, because each of the four $2 times 2$ checkerboards with one square removed can be tiled using one right triomino.
INDUCTIVE STEP: The inductive hypothesis is the assumption that $P(k)$ is true for the positive integer $k$; that is, it is the assumption that every $2^k times 2^k$ checkerboard with one square removed can be tiled using right triominoes.
It must be shown that under the assumption of the inductive hypothesis, $P(k+1)$ must also be true; that is, any $2^{k+1} times 2^(k+1)$ checkerboard with one square removed can be tiled using right triominoes. To see this, consider a $2k+1 times2k+1$ checkerboard with one square removed. Split this checkerboard into four checkerboards of size $2^ktimes2^k$, by dividing it in half in both directions. This is illustrated in Figure 6(??). No square has been removed from three of these four checkerboards. The fourth $2^ktimes2^k$ checkerboard has one square removed, so we now use the inductive hypothesis to conclude that it can be covered by right triominoes. Now temporarily remove the square from each of the other three $2^k times 2^k$ checkerboards that has the center of the original, larger checkerboard as one of its corners. By the inductive hypothesis, each of these three $2^k times2^k$ checkerboards with a square removed can be tiled by right triominoes. Furthermore, the three squares that were temporarily removed can be covered by one right triomino. Hence, the entire $2^{k+1} times 2^{k+1}$ checkerboard can be tiled with right triominoes. We have completed the basis step and the inductive step.
Therefore, by mathematical induction $P(n)$ is true for all positive integers $n$. This shows that we can tile every $2^n times 2^n$ checkerboard, where $n$ is a positive integer, with one square removed, using right triominoes.
Solution: Let $P(n)$ be the proposition that every $2^n times2^n$ checkerboard with one square removed can be tiled using right triominoes. We can use mathematical induction to prove that $P(n)$ is true for all positive integers $n$.
BASIS STEP: $P(1)$ is true, because each of the four $2 times 2$ checkerboards with one square removed can be tiled using one right triomino.
INDUCTIVE STEP: The inductive hypothesis is the assumption that $P(k)$ is true for the positive integer $k$; that is, it is the assumption that every $2^k times 2^k$ checkerboard with one square removed can be tiled using right triominoes.
It must be shown that under the assumption of the inductive hypothesis, $P(k+1)$ must also be true; that is, any $2^{k+1} times 2^(k+1)$ checkerboard with one square removed can be tiled using right triominoes. To see this, consider a $2k+1 times2k+1$ checkerboard with one square removed. Split this checkerboard into four checkerboards of size $2^ktimes2^k$, by dividing it in half in both directions. This is illustrated in Figure 6(??). No square has been removed from three of these four checkerboards. The fourth $2^ktimes2^k$ checkerboard has one square removed, so we now use the inductive hypothesis to conclude that it can be covered by right triominoes. Now temporarily remove the square from each of the other three $2^k times 2^k$ checkerboards that has the center of the original, larger checkerboard as one of its corners. By the inductive hypothesis, each of these three $2^k times2^k$ checkerboards with a square removed can be tiled by right triominoes. Furthermore, the three squares that were temporarily removed can be covered by one right triomino. Hence, the entire $2^{k+1} times 2^{k+1}$ checkerboard can be tiled with right triominoes. We have completed the basis step and the inductive step.
Therefore, by mathematical induction $P(n)$ is true for all positive integers $n$. This shows that we can tile every $2^n times 2^n$ checkerboard, where $n$ is a positive integer, with one square removed, using right triominoes.
edited Dec 8 at 0:18
dantopa
6,41132042
6,41132042
answered Dec 7 at 22:03
kiro malak
11
11
You have added nothing new to the already existing answers.
– José Carlos Santos
Dec 7 at 22:24
add a comment |
You have added nothing new to the already existing answers.
– José Carlos Santos
Dec 7 at 22:24
You have added nothing new to the already existing answers.
– José Carlos Santos
Dec 7 at 22:24
You have added nothing new to the already existing answers.
– José Carlos Santos
Dec 7 at 22:24
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.
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%2f461252%2fproof-a-2n-by-2n-board-can-be-filled-using-l-shaped-trominoes-and-1-monomi%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
NX,77ng2DB,wY34Jkj kAa
What exactly are your "L"-shapes? Half the border of a $4times 3$ rectangle? Or which dimensions?
– AlexR
Aug 6 '13 at 17:22
3
Are you perhaps trying to show that a $2^ntimes 2^n$ board can't be filled by trominoes and one monomino? It's totally obvious that trominoes can't fill an $8times 8$ board because 3 does not divide 64; on the other hand, they can fill a $6times 6$ board quite easily. For the $2^ntimes 2^n$ case, see mutilated chessboard problem.
– MJD
Aug 6 '13 at 17:28
3
@alexr "L-shaped tromino" is a clear and unambiguous piece of jargon in combinatorial geometry and is easy to look up on the Internet.
– MJD
Aug 6 '13 at 17:29
My mistake; the mutilated chessboard problem is something else.
– MJD
Aug 6 '13 at 17:42
2
You might enjoy trying to cover a $9times 9$ board with 27 trominoes. I found it surprisingly tricky.
– MJD
Aug 6 '13 at 18:27