Mutilated chessboard problem.
The problem is the folkloric one: given a chessboard with two diagonally opposite corners removed, can you tile it with dominoes? A domino is a rectangle which is the size of two adjacent squares. (If you haven't seen it, think about it; the solution is in the article.)
I've known this problem for as long as I can remember, but I didn't realize it had a name. I didn't realize it needed a name. But apparently it's a standard example of a theorem which is hard for automated theorem-proving programs, so that community needed something to call it, because they can't refer to "that one with the dominoes on the chessboard where you get rid of two squares" in the title of their papers.
Harder question, again if you haven't seen it before: when can you remove two squares and have there be a tiling? (I know the answer. If you want to know it, leave a comment.)
Even harder question: when can you remove four squares and have there be a tiling? This might not be that difficult, but I don't know the answer. (It'll give me something to think about on the walk into school this morning, though.)
Subscribe to:
Post Comments (Atom)
6 comments:
I've seen this problem before and I know the solution to the original problem, but I'm not quite sure about the other two (the general rules). I hope I've got it, at least the obvious choice, but I'm racking my brain to be sure it's possible. Ha....maybe I'll give that original problem to my 7th-Graders some day when they finish a quiz. That ought to keep them busy for quite a while
The chessboard is made of black and white squares, where no single color is side by side. Make your domino half black, half white. The rest is intuitive.
Color squares black and white in the usual way. It is easy to see that if two squares of the same color are removed, then tiling is impossible. Is a tiling always possible if two squares of different colors are removed?
OOppsy7, it's not necessarily that intuitive. You can't place your dominoes willy-nilly and expect to cover the whole board, no matter what its shape. There's still more work to do.
Yes any 2 different colored squares remove will yield a tileable board.
Draw any "path" that goes through all squares exactly once and finishing the same square you began.
The path gives a way to tile the board (actually 2 ways) by always placing dominoes on the path direction (that is, each ominio covering 2 adjacent squares on the path).
Remove 2 different colored squares.
That splits the path in 2 disjoint subpaths, each one having an even length (this is where diff colors matter).
Retile the 2 subpaths with the same method and violá! you've tile the mutilated board
Post a Comment