Results 1 to 2 of 2

Math Help - The Domino Problem(tiling)????

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    5

    The Domino Problem(tiling)????

    Hi
    I have a logic coursework which is about the domino problem (problem of deciding whether a given set of tiles admits a tiling), and I dont understand properly what the problem is... Can someone give me an easy explanation of what it is.

    Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,454
    Thanks
    1868
    Quote Originally Posted by alireza1989 View Post
    Hi
    I have a logic coursework which is about the domino problem (problem of deciding whether a given set of tiles admits a tiling), and I dont understand properly what the problem is... Can someone give me an easy explanation of what it is.

    Thank you
    A domino is a rectangle twice as long as it is wide. It should be obvious that if you have a tile that is a square with side length equal to the width of the domino, a domino won't fit on it- the domino is too big. If your tile is a rectangle with width equal to that of a domino and length twice that, obviously one domino will fit that exactly. Just as obviously, you cannot fit dominoes onto a rectangle with width equal to that of the domino and rectangle three times the width. In fact, it should not be difficult to see that you can fit dominos onto a rectangle that is the same width as a the domino and an any even multiple of that in length, but not if its length is an odd multiple of the width.

    How you would determine whether a particular tile can be covered by dominos depends strongly upon the tile.

    But here's a famous example. (I hope it's not YOUR problem!) Suppose you have an 8 by 8 chess board and your dominos have width equal to the width of 1 square and length equal to two such widths. It should be obvious that such a board can be covered by dominos (because each row can be covered by 4 dominos). Now remove two diagonally opposite squares. Can that be covered by dominos? If we had removed just one square the answer would be "obviously not" because there would be an odd number of squares to cover and each domino covers two squares. But removing two squares leaves an even number of squares so it still might be possible to cover a board with opposite corners removed.

    Now suppose the board is colored like a standard chess board, alternating colors. Each domino will cover two DIFFERENT colors but removing the opposite corners we have removed two square of the same color. Since there are not, now, the same number of squares of each color, it is impossible to cover this by dominos.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Geometric Tiling
    Posted in the Geometry Forum
    Replies: 0
    Last Post: October 9th 2011, 09:07 PM
  2. Chess board and 2x1 domino stones.
    Posted in the Math Puzzles Forum
    Replies: 0
    Last Post: July 27th 2011, 05:09 PM
  3. Replies: 2
    Last Post: September 27th 2010, 10:26 AM
  4. Tiling a chessboard
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 2nd 2009, 04:44 PM
  5. Domino Tiling
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 24th 2008, 04:02 PM

Search Tags


/mathhelpforum @mathhelpforum