mutilated chessboard variations

bossk171 · 2009-02-18 09:51:40

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 64-1=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 (2009-02-18 09:52:53)

mathsyperson · 2009-02-18 10:53:01

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[sup]n[/sup] x 2[sup]n[/sup] chessboard with any one of its squares removed, it is possible to completely cover using L-shaped trionimoes.
(Your second question is a specific case of this.)

bossk171 · 2009-02-18 13:19:03

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.

mathsyperson · 2009-02-19 00:00:23

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 top-right corner was missing instead.

bossk171 · 2009-02-19 04:24:32

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.

TheDude · 2009-02-19 04:58:34

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 top-right 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.

mathsyperson · 2009-02-19 05:34:03

Sorry for being confusing.
All I meant was to draw the lines from bottom-left to top-right, instead of how you had them.

TheDude · 2009-02-19 05:53:40

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 bottom-right 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 bottom-left 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 bottom-right 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 bottom-right 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 top-right instead of top-left, 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.

mathsyperson · 2009-02-19 06:44:42

Yep, that works.
I solved it by observing that 4 L-shaped trionimoes can fit together to make a double-sized block:

 - - - - 
|   |   |
   - -  
| |   | |
 -   - -
| | |
   - 
|   |
 - -

Fitting 4 of the size-2 blocks together will create a size-4 block, and so iterating this can get any size-2^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^(n-1) x 2^(n-1).
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)

bossk171 · 2009-02-19 10:16:00

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 (2009-02-19 10:22:03)

mathsyperson · 2009-02-19 12:33:35

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.

Math Is Fun Forum

#1 2009-02-18 09:51:40

mutilated chessboard variations

#2 2009-02-18 10:53:01

Re: mutilated chessboard variations

#3 2009-02-18 13:19:03

Re: mutilated chessboard variations

#4 2009-02-19 00:00:23

Re: mutilated chessboard variations

#5 2009-02-19 04:24:32

Re: mutilated chessboard variations

#6 2009-02-19 04:58:34

Re: mutilated chessboard variations

#7 2009-02-19 05:34:03

Re: mutilated chessboard variations

#8 2009-02-19 05:53:40

Re: mutilated chessboard variations

#9 2009-02-19 06:44:42

Re: mutilated chessboard variations

#10 2009-02-19 10:16:00

Re: mutilated chessboard variations

#11 2009-02-19 12:33:35

Re: mutilated chessboard variations

Board footer