
 bossk171
 Power Member
mutilated chessboard variations
The mutilated chessboard problem is a very popular classic math puzzle. If you're not familiar with it, google "mutilated chessboard" and read the proof as to why it's impossible, it's pretty cool. Essentially it boils down to the question, "If two opposing corners of a chessboard are removed, can the mutilated board be completely covered with 31 dominoes in such a way that each domino covers 2 squares?"
Let's discuss variations on this problem here!
Variation 1: Consider an 8x8 chessboard with one corner missing (so a total of 641=63 squares). Can it be covered with 21 triominoes (dominoes that are 3*1 squares instead of the traditional 2*1)? What if the triominoes are in an L shape instead of a line?
Board with one corner missing: ______________ ________ ________ ________ ________ ________ ________ ________ _______ __ _____ __ triomino: ___ trinomino (L variation): __
Based on playing around with pictures my suspicions are no, a board with a missing corner piece cannot be covered, but I lack a proof.
So go ahead, post your variations here!
(PS: anyone who wants to produce some legitimate pictures as apposed to my sloppily typed one is more than encouraged to).
Last edited by bossk171 (20090219 08:52:53)
There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction.
Re: mutilated chessboard variations
It's impossible for the straight trionimo. The proof is similar to the standard one, just label the board with three colours instead of two.
One of my favourite problems is this one:
Prove that given a 2^{n} x 2^{n} chessboard with any one of its squares removed, it is possible to completely cover using Lshaped trionimoes. (Your second question is a specific case of this.)
Why did the vector cross the road? It wanted to be normal.
 bossk171
 Power Member
Re: mutilated chessboard variations
mathsyperson wrote:It's impossible for the straight trionimo. The proof is similar to the standard one, just label the board with three colours instead of two.
I tried that, but I'm pretty sure I missed something:
A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C A B C
There are 21 each of A,B and C. The original proof relied on there be a different number A squares and B squares.
There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction.
Re: mutilated chessboard variations
You just got unlucky. There's a difference if you label it using antidiagonal stripes. Alternatively, consider what would happen on your diagram if the topright corner was missing instead.
Why did the vector cross the road? It wanted to be normal.
 bossk171
 Power Member
Re: mutilated chessboard variations
Isn't how I color it arbitrary? I purposely removed that spot because it would give me 21 each of A,B, and C.
When yo say antidiagonal, do you mean vertical or horizontal? If so, I would think that wouldn't make sense... I tried to "color" it so that any triomino place would have to cover and A, B, and C (like a domino has to cover a black and a white). If I cover it vertically than it would be possible to lay a triomino that would cover 3 As (or Bs or Cs) which doesn't seem right...
I'm not trying to be difficult, I honestly am having trouble getting this. Am I missing something very simple... I think am.
There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction.
Re: mutilated chessboard variations
I'm not sure what he means by antidiagonal stripes, but do consider his second point. If you reinsert the A that you removed and instead remove the B in the topright corner of the board you'll get a board with 22 A's, 20 B's, and 21 C's. Since it's still setup such that every straight triomino will have to cover exactly 1 A, B, and C, you can once again see that no such covering is possible.
Wrap it in bacon
Re: mutilated chessboard variations
Sorry for being confusing. All I meant was to draw the lines from bottomleft to topright, instead of how you had them.
Why did the vector cross the road? It wanted to be normal.
Re: mutilated chessboard variations
That is an interesting problem mathsy. Unfortunately I'm not familiar with giving rigorous proofs of something like this, but I can see it visually.
First thing is to show that you can cover any 2^n X 2^n board with a corner square missing. n = 0 is a trivial case, so let's look at n = 1. We have a 2 X 2 board, and since all 4 squares are corners we can assume WLOG that the bottomright square is missing, so our board looks like
X X X _
It's quite obvious how we place our triomino to cover the remaining squares on the board. So now we know how to do a 2 X 2 board. Let's see what happens when we turn that into a 4 X 4 board, again only considering cases where the bottomleft square is removed:
X X X X X X X X X X X X X X X _
Let's place our first triomino the same way that we did in the 2 X 2 case (H represents squares covered by a triomino):
X X X X X X X X X X H H X X H _
Let's pretend that the board is divided into four 2 X 2 squares. The bottomright square is either covered by a triomino or has an empty square. That leaves us with three 2 X 2 squares to cover. How can we do that? By placing another triomino such that each of the 3 tiles that it covers are corner squares to one of the 2 X 2 squares:
X X X X X H H X X H H H X X H _
Now those other three 2 X 2 squares are identical to our original 2 X 2 board problem, which we already know how to solve. Thus, we now know how to solve a 4 X 4 board.
How do we do an 8 X 8 board? We use the same trick as before. We mentally divide the board into four 4 X 4 boards. We can solve the bottomright board with the method we just used, which will leave us with three other completely uncovered 4 X 4 boards. If we place our next triomino such that each tile covers a corner of one of the remaining 4 X 4 boards they'll each become idential to the original 4 X 4 board problem, which we already know how to solve. Covering those gives us a completely filled 8 X 8 board. The process can continue indefinitely to any 2^n X 2^n board.
Now, mathsy's actual question was to show that it could be done with any square missing. This is actually not much of an issue thanks to how triominoes work. Let's say that instead of the lower left corner tile being removed, we actually removed the piece immediately to the left of that piece. Here's what that would look like on a 4 X 4 board:
X X X X X X X X X X X X X X _ X
To solve this new problem we can simply rotate our first triomino such that the corner tile is in the topright instead of topleft, so it would look like this:
X X X X X X X X X X H H X X _ H
Notice that once again we are left with a completed 2 X 2 board in the bottom right, so the rest of our 4 X 4 solution can remain unchanged. The same thing goes for if we move the empty square one tile up:
X X X X X X X X X X _ H X X H H
Any other tile that is removed from the 4 X 4 board is just a reflection or rotation of what we've just shown, so now we can solve a 4 X 4 board with any square missing. And if we can solve any 4 X 4 board with a missing square we can generalize that to the 8 X 8 case, since we need solve only one 4 X 4 board and then we add a triomino that turns the other three parts of the board into the "corner missing" case. And if we can do any 8 X 8 board we can do any 16 X 16 board, etc.
Wrap it in bacon
Re: mutilated chessboard variations
Yep, that works. I solved it by observing that 4 Lshaped trionimoes can fit together to make a doublesized block:
Fitting 4 of the size2 blocks together will create a size4 block, and so iterating this can get any size2^n block you want.
So then given a 2^n x 2^n chessboard, you can place a block of appropriate size on it so that the removed square isn't covered, and you're left with the same problem, only now the chessboard is 2^(n1) x 2^(n1). Do this until there's only a 2x2 board left, and then place one final block to finish the covering.
(This can be rephrased as a proof by induction if you want to be formal about it)
Why did the vector cross the road? It wanted to be normal.
 bossk171
 Power Member
Re: mutilated chessboard variations
Cool proof TheDude.
How about if any two (oppositely colored) squares are removed on and 8x8 board (or more generally a 2^n x 2^n board) can it still be covered with dominoes? I haven't put any thought into this yet, I just want to keep up the momentum. I would think that the proof would be a lot the one The Dude wrote for Mathsyperson's variation, but with minor changes...
EDIT: I like Mathsyperson's proof too, it just took me a few more minutes to get it.
Last edited by bossk171 (20090220 09:22:03)
There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction.
Re: mutilated chessboard variations
Interesting question! A few minutes of scribbling leads me to think it's probably possible, because there aren't any easy counterexamples I can find.
Edit: I haven't figured out exactly how to work it, but I think laying dominoes to make a rectangle such that the two removed squares are opposite corners would be a good start. Also, I'm pretty sure it's possible for all boards of length 2n, not just the 2^n ones.
Edit2: I came across a much nicer way today. First draw a snakey path so on the board so that all squares are covered, and the path starts and finishes in the same square. Cover the board with dominoes by following this path, and then once two of the squares have been removed, you can get the new solution by removing a domino and shifting.
Why did the vector cross the road? It wanted to be normal.
