Proof a $2^n$ by $2^n$ board can be filled using L shaped trominoes and 1 monomino

Multi tool use
Multi tool use












1














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.










share|cite|improve this question
























  • 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
















1














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.










share|cite|improve this question
























  • 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














1












1








1


1





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.










share|cite|improve this question















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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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


















  • 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










3 Answers
3






active

oldest

votes


















11














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.






share|cite|improve this answer























  • 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





















1














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.



enter image description hereenter image description here






share|cite|improve this answer





























    -1














    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.






    share|cite|improve this answer























    • You have added nothing new to the already existing answers.
      – José Carlos Santos
      Dec 7 at 22:24











    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
    });


    }
    });














    draft saved

    draft discarded


















    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









    11














    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.






    share|cite|improve this answer























    • 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


















    11














    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.






    share|cite|improve this answer























    • 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
















    11












    11








    11






    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.






    share|cite|improve this answer














    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.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    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




















    • 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













    1














    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.



    enter image description hereenter image description here






    share|cite|improve this answer


























      1














      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.



      enter image description hereenter image description here






      share|cite|improve this answer
























        1












        1








        1






        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.



        enter image description hereenter image description here






        share|cite|improve this answer












        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.



        enter image description hereenter image description here







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Mar 13 '17 at 8:28









        Takahiro Waki

        2,073620




        2,073620























            -1














            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.






            share|cite|improve this answer























            • You have added nothing new to the already existing answers.
              – José Carlos Santos
              Dec 7 at 22:24
















            -1














            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.






            share|cite|improve this answer























            • You have added nothing new to the already existing answers.
              – José Carlos Santos
              Dec 7 at 22:24














            -1












            -1








            -1






            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.






            share|cite|improve this answer














            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.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            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


















            • 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


















            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            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





















































            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
            HVEgcZcXS6wqjF7H,HpuO7QPB6wopfJaWecK7XgCopKx

            Popular posts from this blog

            Bressuire

            Cabo Verde

            Gyllenstierna