A Domino-Covering Problem

I do not remember where I saw this problem.

Problem. Invent a connected shape made out of squares on the square grid that cannot be cut into dominoes (rectangles with sides 1 and 2), but if you add a domino to the shape then you can cut the new bigger shape.

This problem reminds me of another famous and beautiful domino-covering problem.

Problem. Two opposite corner squares are cut out from the 8 by 8 square board. Can you cover the remaining shape with dominoes?

The solution to the second problem is to color the shape as a chess board and check that the number of black and white squares is not the same.

What is interesting about the first problem is that it passes the color test. It made me wonder: Is there a way to characterize the shapes on a square grid that pass the color test, but still can’t be covered in dominoes?

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

9 Comments

  1. Oscar Cunningham:

    I can’t remember what paper I saw this in, but several examples of regions where the colouring argument fails can be made from “dumbbell” shapes, Get two large regions, one with too many white squares and one with two many black squares and connect them by a thin bridge. There will be a balanced number of colours overall, but one will always be able to find a cut across the bridge that puts too many white squares on one side and black squares on the other.

  2. tanyakh:

    Oscar, thanks. That makes sense.

  3. Simon Rubinstein-Salzedo:

    Answer to your final question: Yes, there is: the Hall Marriage Theorem.

  4. Colin Wright:

    Tanya, I spoke about exactly this at G4G many years ago, and submitted a paper. Is that perhaps what you saw?

    Best,

    Colin.

  5. tanyakh:

    Colin, can you sent me your paper? I think I saw this puzzle in Russian somewhere recently.

  6. impartial james:

    There is a nice algorithm to determine if a simply connected region can be tiled by dominos, which I’ve adapted from http://timo.jolivet.free.fr/docs/ThurstonLectNotes.pdf.

    Color the interior squares of R black and white in checkerboard fashion, and check if it passes the color test. If so, pick an arbitrary vertex on the boundary and label it zero. Trace clockwise around the boundary. As you go around, label each vertex with the previous label plus one when you pass a white square, and with the previous label minus one when you pass a black square. Once all the border vertices are labeled, find a vertex v with a minimal label; this will not occur on a corner. Place a domino so v is on the midpoint of its long side. What remains is a smaller region (or regions, if the added domino disconnects the region), so this procedure can be recursively applied to the remainder (really, you don’t need to recompute the border labels, only local adjustments need to be made near the added domino).

  7. James Pfeiffer:

    The even/odd test and the color test are both global, but there can be local obstructions too, e.g. a “plus sign” shape as below, no matter what the rest of the region looks like.

    _X_
    XXX
    _X_

  8. Colin Wright:

    Hi Tanya,

    I think I have your email somewhere – I’ll try to find it and send you the paper.
    If you can email me then it will be easier … I have the paper to hand.

    Cheers,

    Colin

  9. Colin Wright:

    OK! Papers found and sent. Let me know if I can help further.

    Best,

    Colin