A classic math puzzle!

[KnifeMissile]

I've wanted to post this puzzle for a while now but, first, let's say down some terminology.

A chessboard is what we all think of as a chessboard except that we are not concerned with the colour of the squares and it's dimensions needn't necessarily be 8 x 8. A triominoe is a piece that consists of three chessboard squares connected together in an L shape. Finally, a chessboard is said to be defective if it is missing exactly one square.

Now, prove that every 2^n x 2^n defective chessboard can be tiled with triominoes...

[passthru]

I'm confused.
If n=0, the board is 1 square and a triominoe can't fit.
If n=1, the board is 2x2 and a triominoe can't fit.
If n=2, the board is 4x4 and I'm not going to visualize the triominoes on it because 4x4 is 16 spaces but triominoes that take 3 spaces can't be added together to take 16 spaces since it's not a multiple of 3.

And damnit I'm tired cause I didn't read the "defective" part. I'll assume that the question excludes the case where n=0, and take a look tomorrow.

[Kadath]

Well, in the case where n=0, the board is 0 squares, so...
Hmm. I'm at 4x4 and I think I found a case where you can't do it, which is clearly wrong. Assuming piece (3,2) is missing, how do you tile it with triominoes?

[rsl12]

interesting question. i will have to think about that one knifemissile.

[Yakk]

pass, in the n=0 case, there is exactly one defective chessboard.

The empty chessboard.

Which can have all of its squares covered with triominoes: you use 0 triominoes to cover all 0 squares.

[Shpoop]

i know this probably isnt a sufficient proof, but (2^n)(2^n) - 1 is always divisible by 3

and kadath, here u go:
[img]http://groups.msn.com/_Secure/0SgAAAKQWfl2Jq7ic8vj!w0HN!*LKCR1J77UA7yPkM6E2xDSO2XnDGh!IZU!kAl08E2Ho3jzYK0jfJtYs*UYL4gBoVFZwHd8MFwuNpItlR*rV!W*1Q9euKg/trinome.JPG?dc=4675464204921035879[/img]

[Kadath]

Oh, my. I feel extraordinarily stupid now.

[KnifeMissile]

Thank you, so much, Shpoop! That illustration was brilliant!

[rsl12]

ok, i have a proof! it's recursive, i don't know if i can explain it without diagrams.

trivial case: 2x2 should be obvious.

4x4: a 4x4 is made up of 4 2x2 squares. Let's divide it into NW, NE, SW, SE quadrants. The defective square will be in one of those quadrants, let's say in the NW, and since we've already proved that a 2x2 defective square can be tiled, the NW quadrant can be completely tiled. For the remaining 3 quadrants, pretend that the 3 tiles closest to the center of the big 4x4 square are defective. Then you can tile the each of those quadrants, since they're all defective 2x2 squares. Finally, stick the final tile right in the center, in the three tiles you pretended were defective, and you're done!

8x8: Same logic. Divide into four 4x4 quadrants. Whichever quadrant has the defective square can be tiled (as proved above). Pretent the remaining center squares are defective, tile the other three quadrants. Put the final tile in the center.

Etc etc etc. Is there a better proof?

[KnifeMissile]

That's pretty much it! If you wanted to formalize the proof, use mathematical induction!

I believe this is the first time anyone has ever solved one of my posted puzzles...

[rsl12]

that was a great puzzle knifemissile. i kept going in the wrong direction over and over again, because it reminds me of this puzzle:

Again we have a defective chessboard that needs tiling. In this case, the defective chessboard is formed by taking a NxN square and then adding one more row of N-2 squares, centering it. This time we're actually using dominoes (2x1 dominoes). Prove that for any NxN chessboard, you can only tile it if N is even.

EDITED! made a mistake 1st time i posted. sorry about that.

[rsl12]

For example: if N = 4,

___XXXX___
___XXXX___
___XXXX___
___XXXX___
____XX____

[KnifeMissile]

Ooh, tricky. I'll need to think about this one...

[KnifeMissile]

Well, as usual, I was about to type in my proof (which I thought was elegant, considering) and my boss comes by to check up on me. We have a good relationship so I show him the problem and give him my proof, but then he thinks about it... and comes up with a better proof! I can't tell you how often this has happend...


Colour the defective chessboard with a chess colouring (one of two colours, no square has the same colour as it's adjacent square). If the shape is tiled with dominoes, then there must be an equal number of black and white squares on the board. However, because the width of the chessboard is odd, two squares of the same colour have been removed. Therefore, the board cannot be tiled with dominoes.
QED

[rsl12]

knifemissile, that's the proof i would give too. what was your other one?

[KnifeMissile]

It was a constructive proof.

Basically, the defective row forces a partition of the next row because it has a run of odd length starting from an odd column. I called this a class D row.

The next row is partitioned into two runs of odd length, both starting from even columns. Because both runs are odd length, this forces the next row to be partitioned by two dominoes. Because both runs start from even columns, the next row must have a run of odd length starting from an odd column. I called this a class P row.

As you can see, all P rows are followed by D rows, while all D rows are followed by P rows. Couple this with the fact that both rows must have, at least, one domino jutting up from them, this shows that no tiling of this shape exists...
QED

[rsl12]

not sure that proof is right--it assumes that dominoes you can have only one or two 'partitions'. it proves that you can't tile it if you tile it in that particular way, but not if you put three or more partitions in a given row. glad you found the other proof though.

[KnifeMissile]

The proof is fine. I just gave an overview of it to give you an idea of how it worked. Typing out the whole proof with all it's rigour would have been annoying. Besides, I figured you could figure it out. I guess I'm not used to such an adversarial attitude...

For instance, it's not that you can only have one or two "partitions," it's that you are forced to have, at least, one or two partitions. The addition of extra partitions doesn't remove the properties of the first few partitions that the proof was relying on.

[rsl12]

sorry, i guess i just didn't understand it fully then.

thanks for making me feel dumb

[cowudders14]

Must brush up on my maths...
I have a degree in Civil Engineering and was pondering those! Grr...