Cover Chessboard with Domino Tiles












6














I have a question about a mathematical riddle which I already solved but still looking for a shorter/simpler solution:



Following problem: We consider a standard $8 times 8$ chessboard and we cover it (completely!) with dominos of size $2 times 1$ (therefore every domino tile cover exactly $2$ fields).



The question is if we can find a cover such that there doesn't exist a $2 times 2$ subsquare which is covered exactly by two domino tiles or in other words in the cover there don't occure two "direct" neighbour domino tiles from following shape:



enter image description here



I have it already solved in following way: I claim that such covering isn't possible.



Argue via contradiction: Assume that it's possible. Consider the $2 times 2$ squares of the chess board and consider the partial cover of directly neighboured $2 times 2$ squares. If a cover as above really exist then up to symmetry on the common edge of the two neighboured squares there could only occure two following cases (here only the vertical pairs; horizontally: analogous):



enter image description here




  1. The two neighboured squares share a common domino tile (the orange one)


  2. they don't share any domino tile on the common edge



Now there are exactly $24$ such pairings between neighboured $2 times 2$ squares (note we don't consider the diagonal neighbour pairs).



Now we count all domino tiles in following way:



-each pair of neighbour squares which share a unique common domino tile contribute a $1$ (the orange one)



-each pair of neighbour squares don't share a common domino tile contribute a $1$ with the unique tile beeing fully contained in only one square and intersecting the common edge (the grey one).



That's all. But then we get only $24$ tiles althought there are $32$. Contradiction.



I guess this argument works but I think that it's too cumbersome. Does anybody have an easier / not too circumstaneous way to show it?










share|cite|improve this question
























  • mathworld.wolfram.com/PerfectMatching.html
    – Ethan
    2 hours ago
















6














I have a question about a mathematical riddle which I already solved but still looking for a shorter/simpler solution:



Following problem: We consider a standard $8 times 8$ chessboard and we cover it (completely!) with dominos of size $2 times 1$ (therefore every domino tile cover exactly $2$ fields).



The question is if we can find a cover such that there doesn't exist a $2 times 2$ subsquare which is covered exactly by two domino tiles or in other words in the cover there don't occure two "direct" neighbour domino tiles from following shape:



enter image description here



I have it already solved in following way: I claim that such covering isn't possible.



Argue via contradiction: Assume that it's possible. Consider the $2 times 2$ squares of the chess board and consider the partial cover of directly neighboured $2 times 2$ squares. If a cover as above really exist then up to symmetry on the common edge of the two neighboured squares there could only occure two following cases (here only the vertical pairs; horizontally: analogous):



enter image description here




  1. The two neighboured squares share a common domino tile (the orange one)


  2. they don't share any domino tile on the common edge



Now there are exactly $24$ such pairings between neighboured $2 times 2$ squares (note we don't consider the diagonal neighbour pairs).



Now we count all domino tiles in following way:



-each pair of neighbour squares which share a unique common domino tile contribute a $1$ (the orange one)



-each pair of neighbour squares don't share a common domino tile contribute a $1$ with the unique tile beeing fully contained in only one square and intersecting the common edge (the grey one).



That's all. But then we get only $24$ tiles althought there are $32$. Contradiction.



I guess this argument works but I think that it's too cumbersome. Does anybody have an easier / not too circumstaneous way to show it?










share|cite|improve this question
























  • mathworld.wolfram.com/PerfectMatching.html
    – Ethan
    2 hours ago














6












6








6







I have a question about a mathematical riddle which I already solved but still looking for a shorter/simpler solution:



Following problem: We consider a standard $8 times 8$ chessboard and we cover it (completely!) with dominos of size $2 times 1$ (therefore every domino tile cover exactly $2$ fields).



The question is if we can find a cover such that there doesn't exist a $2 times 2$ subsquare which is covered exactly by two domino tiles or in other words in the cover there don't occure two "direct" neighbour domino tiles from following shape:



enter image description here



I have it already solved in following way: I claim that such covering isn't possible.



Argue via contradiction: Assume that it's possible. Consider the $2 times 2$ squares of the chess board and consider the partial cover of directly neighboured $2 times 2$ squares. If a cover as above really exist then up to symmetry on the common edge of the two neighboured squares there could only occure two following cases (here only the vertical pairs; horizontally: analogous):



enter image description here




  1. The two neighboured squares share a common domino tile (the orange one)


  2. they don't share any domino tile on the common edge



Now there are exactly $24$ such pairings between neighboured $2 times 2$ squares (note we don't consider the diagonal neighbour pairs).



Now we count all domino tiles in following way:



-each pair of neighbour squares which share a unique common domino tile contribute a $1$ (the orange one)



-each pair of neighbour squares don't share a common domino tile contribute a $1$ with the unique tile beeing fully contained in only one square and intersecting the common edge (the grey one).



That's all. But then we get only $24$ tiles althought there are $32$. Contradiction.



I guess this argument works but I think that it's too cumbersome. Does anybody have an easier / not too circumstaneous way to show it?










share|cite|improve this question















I have a question about a mathematical riddle which I already solved but still looking for a shorter/simpler solution:



Following problem: We consider a standard $8 times 8$ chessboard and we cover it (completely!) with dominos of size $2 times 1$ (therefore every domino tile cover exactly $2$ fields).



The question is if we can find a cover such that there doesn't exist a $2 times 2$ subsquare which is covered exactly by two domino tiles or in other words in the cover there don't occure two "direct" neighbour domino tiles from following shape:



enter image description here



I have it already solved in following way: I claim that such covering isn't possible.



Argue via contradiction: Assume that it's possible. Consider the $2 times 2$ squares of the chess board and consider the partial cover of directly neighboured $2 times 2$ squares. If a cover as above really exist then up to symmetry on the common edge of the two neighboured squares there could only occure two following cases (here only the vertical pairs; horizontally: analogous):



enter image description here




  1. The two neighboured squares share a common domino tile (the orange one)


  2. they don't share any domino tile on the common edge



Now there are exactly $24$ such pairings between neighboured $2 times 2$ squares (note we don't consider the diagonal neighbour pairs).



Now we count all domino tiles in following way:



-each pair of neighbour squares which share a unique common domino tile contribute a $1$ (the orange one)



-each pair of neighbour squares don't share a common domino tile contribute a $1$ with the unique tile beeing fully contained in only one square and intersecting the common edge (the grey one).



That's all. But then we get only $24$ tiles althought there are $32$. Contradiction.



I guess this argument works but I think that it's too cumbersome. Does anybody have an easier / not too circumstaneous way to show it?







recreational-mathematics puzzle






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 2 hours ago

























asked 2 hours ago









KarlPeter

5221313




5221313












  • mathworld.wolfram.com/PerfectMatching.html
    – Ethan
    2 hours ago


















  • mathworld.wolfram.com/PerfectMatching.html
    – Ethan
    2 hours ago
















mathworld.wolfram.com/PerfectMatching.html
– Ethan
2 hours ago




mathworld.wolfram.com/PerfectMatching.html
– Ethan
2 hours ago










1 Answer
1






active

oldest

votes


















10














How about this:



Let's number the rows $1$ through $8$ from top to bottom, and the columns $1$ through $8$ from left to right. Cell $(x,y)$ means the cell in row $x$ and column $y$



You need a tile to cover cell $(1,1)$. This can be done in two ways, but by symmetry, we only have to consider one of these, so let's consider placing it horizontally, i.e. cover cells $(1,1)$ and $(1,2)$:



enter image description here



Now we need to cover cell $(2,1)$. In order to avoid making a $2x2$ subsquare made up of two tiles, there is only way way to place a tile under it, so that will cover cells $(2,1)$ and $(3,1)$:



enter image description here



Now we need to cover $(2,2)$. Again, there is only way way to do this in order to avoid making a $2x2$ subsquare made up of two tiles: cover cells $(2,2)$ and $(2,3)$.



enter image description here



OK, and now keep placing tiles along this basic 'diagonal' of the chess-board: you'll find all the placements are forced if you want to avoid a $2x2$ subsquare made up of two tiles. But, at the end of the diagonal, you end up having to use one tile to cover $(7,6)$ and $(8,6)$, and another one to cover $(7,7)$ and $(7,8)$:



enter image description here



... and now you are forced to also place one on $(8,7)$ and $(8,8)$, and get a $2x2$ subsquare made up of two tiles. (also note that the two parts of the board as of yet uncovered each have an odd number of squares left, so they can no longer be completely covered)



So, it is indeed impossible to do a complete tiling without getting a $2x2$ subsquare made up of two tiles.






share|cite|improve this answer























    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%2f3052354%2fcover-chessboard-with-domino-tiles%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









    10














    How about this:



    Let's number the rows $1$ through $8$ from top to bottom, and the columns $1$ through $8$ from left to right. Cell $(x,y)$ means the cell in row $x$ and column $y$



    You need a tile to cover cell $(1,1)$. This can be done in two ways, but by symmetry, we only have to consider one of these, so let's consider placing it horizontally, i.e. cover cells $(1,1)$ and $(1,2)$:



    enter image description here



    Now we need to cover cell $(2,1)$. In order to avoid making a $2x2$ subsquare made up of two tiles, there is only way way to place a tile under it, so that will cover cells $(2,1)$ and $(3,1)$:



    enter image description here



    Now we need to cover $(2,2)$. Again, there is only way way to do this in order to avoid making a $2x2$ subsquare made up of two tiles: cover cells $(2,2)$ and $(2,3)$.



    enter image description here



    OK, and now keep placing tiles along this basic 'diagonal' of the chess-board: you'll find all the placements are forced if you want to avoid a $2x2$ subsquare made up of two tiles. But, at the end of the diagonal, you end up having to use one tile to cover $(7,6)$ and $(8,6)$, and another one to cover $(7,7)$ and $(7,8)$:



    enter image description here



    ... and now you are forced to also place one on $(8,7)$ and $(8,8)$, and get a $2x2$ subsquare made up of two tiles. (also note that the two parts of the board as of yet uncovered each have an odd number of squares left, so they can no longer be completely covered)



    So, it is indeed impossible to do a complete tiling without getting a $2x2$ subsquare made up of two tiles.






    share|cite|improve this answer




























      10














      How about this:



      Let's number the rows $1$ through $8$ from top to bottom, and the columns $1$ through $8$ from left to right. Cell $(x,y)$ means the cell in row $x$ and column $y$



      You need a tile to cover cell $(1,1)$. This can be done in two ways, but by symmetry, we only have to consider one of these, so let's consider placing it horizontally, i.e. cover cells $(1,1)$ and $(1,2)$:



      enter image description here



      Now we need to cover cell $(2,1)$. In order to avoid making a $2x2$ subsquare made up of two tiles, there is only way way to place a tile under it, so that will cover cells $(2,1)$ and $(3,1)$:



      enter image description here



      Now we need to cover $(2,2)$. Again, there is only way way to do this in order to avoid making a $2x2$ subsquare made up of two tiles: cover cells $(2,2)$ and $(2,3)$.



      enter image description here



      OK, and now keep placing tiles along this basic 'diagonal' of the chess-board: you'll find all the placements are forced if you want to avoid a $2x2$ subsquare made up of two tiles. But, at the end of the diagonal, you end up having to use one tile to cover $(7,6)$ and $(8,6)$, and another one to cover $(7,7)$ and $(7,8)$:



      enter image description here



      ... and now you are forced to also place one on $(8,7)$ and $(8,8)$, and get a $2x2$ subsquare made up of two tiles. (also note that the two parts of the board as of yet uncovered each have an odd number of squares left, so they can no longer be completely covered)



      So, it is indeed impossible to do a complete tiling without getting a $2x2$ subsquare made up of two tiles.






      share|cite|improve this answer


























        10












        10








        10






        How about this:



        Let's number the rows $1$ through $8$ from top to bottom, and the columns $1$ through $8$ from left to right. Cell $(x,y)$ means the cell in row $x$ and column $y$



        You need a tile to cover cell $(1,1)$. This can be done in two ways, but by symmetry, we only have to consider one of these, so let's consider placing it horizontally, i.e. cover cells $(1,1)$ and $(1,2)$:



        enter image description here



        Now we need to cover cell $(2,1)$. In order to avoid making a $2x2$ subsquare made up of two tiles, there is only way way to place a tile under it, so that will cover cells $(2,1)$ and $(3,1)$:



        enter image description here



        Now we need to cover $(2,2)$. Again, there is only way way to do this in order to avoid making a $2x2$ subsquare made up of two tiles: cover cells $(2,2)$ and $(2,3)$.



        enter image description here



        OK, and now keep placing tiles along this basic 'diagonal' of the chess-board: you'll find all the placements are forced if you want to avoid a $2x2$ subsquare made up of two tiles. But, at the end of the diagonal, you end up having to use one tile to cover $(7,6)$ and $(8,6)$, and another one to cover $(7,7)$ and $(7,8)$:



        enter image description here



        ... and now you are forced to also place one on $(8,7)$ and $(8,8)$, and get a $2x2$ subsquare made up of two tiles. (also note that the two parts of the board as of yet uncovered each have an odd number of squares left, so they can no longer be completely covered)



        So, it is indeed impossible to do a complete tiling without getting a $2x2$ subsquare made up of two tiles.






        share|cite|improve this answer














        How about this:



        Let's number the rows $1$ through $8$ from top to bottom, and the columns $1$ through $8$ from left to right. Cell $(x,y)$ means the cell in row $x$ and column $y$



        You need a tile to cover cell $(1,1)$. This can be done in two ways, but by symmetry, we only have to consider one of these, so let's consider placing it horizontally, i.e. cover cells $(1,1)$ and $(1,2)$:



        enter image description here



        Now we need to cover cell $(2,1)$. In order to avoid making a $2x2$ subsquare made up of two tiles, there is only way way to place a tile under it, so that will cover cells $(2,1)$ and $(3,1)$:



        enter image description here



        Now we need to cover $(2,2)$. Again, there is only way way to do this in order to avoid making a $2x2$ subsquare made up of two tiles: cover cells $(2,2)$ and $(2,3)$.



        enter image description here



        OK, and now keep placing tiles along this basic 'diagonal' of the chess-board: you'll find all the placements are forced if you want to avoid a $2x2$ subsquare made up of two tiles. But, at the end of the diagonal, you end up having to use one tile to cover $(7,6)$ and $(8,6)$, and another one to cover $(7,7)$ and $(7,8)$:



        enter image description here



        ... and now you are forced to also place one on $(8,7)$ and $(8,8)$, and get a $2x2$ subsquare made up of two tiles. (also note that the two parts of the board as of yet uncovered each have an odd number of squares left, so they can no longer be completely covered)



        So, it is indeed impossible to do a complete tiling without getting a $2x2$ subsquare made up of two tiles.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited 2 hours ago

























        answered 2 hours ago









        Bram28

        59.9k44187




        59.9k44187






























            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%2f3052354%2fcover-chessboard-with-domino-tiles%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







            Popular posts from this blog

            A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

            Calculate evaluation metrics using cross_val_predict sklearn

            Insert data from modal to MySQL (multiple modal on website)