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.
]]>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.
]]>    
  
 
   
  
  

 
 
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)
]]>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.
]]>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.
]]>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.
]]>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 Lshaped trionimoes.
(Your second question is a specific case of this.)
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).
]]>