Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Tiling problem

  1. May 31, 2005 #1
    Start with a 8 by 8 board of squares (for instance, a chessboard) and take away the top-left and bottom-right corner squares so that there are 62 squares left. Take some dominoes that are the same size as two squares of the chessboard. Can you cover the 62 squares of the board with 31 such dominoes? If so, how? If not, why?
  2. jcsd
  3. May 31, 2005 #2
    Using standard chessboard colouring

    Here is a solution using the standard chessboard colouring(alternate white and black squares).:
    On looking at a chessboard, we can see that the opposite blocks(as mentioned) have the same colour. So, after removing the two squares, we would have
    - 32 white and 30 black squares OR
    - 30 white and 32 black squares

    The two cases are identical (due to symmetry of the chess board). So I will solve only the first.
    Said domino covers two squares. On a chessboard, that means one white and one black square. 31 dominoes will cover 31 white and 31 black squares, but there are only 30 black squares. So 31 dominoes cannot cover the board.
  4. May 31, 2005 #3
    Very good ssj5harsh. You got it. I hope you realize that although the colors are a good way of thinking about the problem, the board doesn't actually need to be colored for the solution to work.
  5. Jun 1, 2005 #4
    actually, if we try, we can cover 6 squares in the chess board using the domino of the 2-chessboard-square size. as the question doesn't mention if we have to cover the square compleately. this way, it is possible, even with less then 31 dominos. if the number (31) in neccesary, we can just use the excess domino to pile up ontop of the other domino or fill uf the empty space.
  6. Jun 2, 2005 #5
    without colouring?

    I have tried as jimmysnyder told me to try without colouring. But I can't arrive at an unambiguous proof. Perhaps someone could guide me about it.
  7. Jun 2, 2005 #6
    If there were a solution without coloring, the same solution would work on the colored board.
  8. Jun 2, 2005 #7
    Think about it as if you had a regular chess board(8x8) full of dominoes(32), in any kind of arrangment. Now try to take away one domino and leave two empty spaces that aren't adjacent.
  9. Jun 2, 2005 #8
    This is not a good way to think of the problem. For instance, take the chess board and remove the top left and top right corner squares. These squares are not adjacent, but the board can easily be covered with the 31 dominoes.
  10. Jun 2, 2005 #9
    touche, just thinking out loud. I'm sure then that it has to do with the shape. Perhaps there has to be an even number of squares in each row.
    edit* not sure if that would work either- no it wouldn't work, i'll think about it later when i have a fresh mind
    Last edited: Jun 2, 2005
  11. Jun 3, 2005 #10

    Ah ha! Im going to try and make this simple =-) you have a 2x2 board. take out 2 diagonal squares. You cant cover the last 2 with one domino. So if you had a 8x8 board and cover the board however you wish. and remove any 2 squares that are at a diagonal. You can rearrange the remaining dominos to get your 2x2 square around them and the board becomes impossible to cover.
  12. Jun 3, 2005 #11
    The shortcoming of this approach is that it can't be extended to different configurations of the problem (besides the fact that I didn't understand it). For instance, if instead of removing the corner squares as in the original problem, we remove two squares from the board that are a knight's move away from each other, then looking at diagonals won't work, but ssj5harsh's solution will.

    In my opinion, the easiest way to look at the problem is as ssj5harsh does in the first solution posted. Each domino must cover both a black and white square. In the problem, the two squares removed were the same color. That is a good and easy to understand solution. My comment about not needing the colors simply meant that this solution works even if the board is colored green and red, or is not colored at all. Just mentally assign colors to each square. Or assign odd and even numbers so that colors don't enter into it. Or do as I had suggested: Note that if you could cover the uncolored board with the dominos then the same solution would apply to the colored board.
  13. Jun 6, 2005 #12
    Ok I reread my solution and I admit it may be a bit confusing... It was a bit of rambling I came up with real quick that mostly described what I was thinking =-) I was trying to come up with a proof that would describe the problem without using the 32 black squares and 30 white squares.

    I was going to try and reiterate the solution here but It would be just as confusing as the first attempt =-(

    Im not sure what you mean by that. removing 2 squares a knights move away from eachother would not be a problem as they would not hinder filling the board with 31 dominos.

    As I said Im trying to come up with a solution that does not require a colord squares aproch. Or for that matter odd/even numbers.
    Last edited by a moderator: Jun 6, 2005
  14. Jun 6, 2005 #13
    Of course you are right. What was I thinking? What I meant was that ssj5harsh's analysis works whenever you remove two squares of the same color whether they are on the same diagonal or not.
    Last edited: Jun 6, 2005
  15. Jun 6, 2005 #14
    In general, it is good to try and come up with new approaches to problems that have already been solved. In this way, new insights are gained. However, if your goal is to come up with an approach that is simpler to understand than ssj5harsh's, I believe you have a daunting task ahead of you.
  16. Jun 6, 2005 #15
    Given any M by N board where M and N are even, that can be covered by 2 by 1 dominos:

    Suppose there is a M by N grid of cells on the board with elements (j,k), with each squared labeled some number P where p is that squares j+k

    Notice that the p’s alternate even an odd. So each domino will cover an even and a odd square.

    The first square (1,1) has an even p.
    The last square (M,N) is also even, since any two evens added equals a even.

    By removing two squares with even p’s two dominos will not be able to be placed.
  17. Jun 6, 2005 #16
    Still the odd even aproch. The must be a better explanation than that.

    Im just gonna sit here pondering it :confused:
  18. Jun 7, 2005 #17


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Odd/even is no different from black/white.

    But it should be clear that the problem can not be solved without retaining some information about the location of the square. The residue, mod 2 of the sum of co-ordinates is one such piece of info...but a necessary (bariing a choice which retains more info) piece, nevertheless.
  19. Jun 8, 2005 #18
    :uhh: I wish jimmy had originally given this board as uncoloured.

    -- AI
  20. Jun 8, 2005 #19
    Your wish was granted even before you made it known to me.
  21. Jun 8, 2005 #20
    Here is what im thinking, even though it may totally be wrong, unclear, and impossible to explain with out pictures...

    Given that the “board” is a even number by an even number in dimension.

    Let there be groupings of the squares on the board such that every square is covered in a rectangular shape i.e. a “box”.

    Now if we were able to place the tiles, one of the following would have to be true for all groupings of boxes:
    i) Every box would be exactly covered by tiles
    ii) There would be excess in ends of tiles in some boxes, overlapping into other boxes

    For any possible grouping of “boxes” that cover the whole board with the two opposite corner squares removed there must be at least one box with “odd sized area” *

    A box with an odd sized area cannot be exactly filled with 2x1 tiles, since the tiles have an even sized area and we are putting n tiles into the box.

    If a box is filled with “left over” parts of tiles hanging over the sides of the “boxes” there must be an odd number of left over parts that end up in other boxes. Which in turn would then give another box an “odd amount of area”. Since we are only considering finite sized boards, some box would have to be left over with odd sized area, which implies it couldn’t be filled with tiles.

    * This is what I haven’t figured out how to show yet, even though im sure it’s true.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook