Checkerboard Problem: Proving No Exact Cover w/ T-Shaped Dominos

[morbius27]

Homework Statement

Consider an 8x8 checkerboard with two squares from each of two opposite corners deleted so that 60 squares are left (i.e the top row has 6 squares with the 2 far right squares missing, and the bottom row has 6 squares left with the 2 far left missing). Prove that the remaining squares cannot be covered exactly by T-shaped dominos consisting of four squares and their rotations.

I figured that if the domino is centered on a white piece, then its must cover 3 black pieces surrounding it, and vice versa. this would mean that centering the domino on 10 white pieces automatically covers the 30 black pieces, and thus there is no way to cover the remaining 20 white pieces. Unfortunately, I don't know how to formalize this proof and show that this must be the case.

 

[tiny-tim]

Hi morbius27!

It might be easier to start by considering how many Ts are needed.

 

[morbius27]

Hi morbius27!

It might be easier to start by considering how many Ts are needed.

well, then obviously 15 Ts would be needed to cover the board, since there are 60 spots and 4 squares to a T. If you alternated centering them on white then black pieces, the 14th one would give 28 covered for both black and white. But since two of each are left, and a T requires 1 w/b and 3 b/w, then it obviously fails...is there any way to show this in a proof format?

 

[tiny-tim]

Yes, you've almost proved it.

Now use the fact that difference between the number of white and black squares for each T is always ±2.

 

[morbius27]

Yes, you've almost proved it.

Now use the fact that difference between the number of white and black squares for each T is always ±2.

Ahh, that does definitely make sense, but how can I show that the optimum way of putting down the Ts is by alternating centering them on black and white squares. i.e. why is that method favorable to, say, centering the first 8 on white then the rest on black, or something similar?

 

[tiny-tim]

What's 15 times ±2 ?

 

[morbius27]

What's 15 times ±2 ?

well 30 of course =P. So what you're saying is that in order to cover the entire board, the T would have to cover two white and two black, but since it covers 1 white and 3 black (or vice versa) there will always be two left over from each color in the end?

 

[tiny-tim]

… since it covers 1 white and 3 black (or vice versa) there will always be two left over from each color in the end?

I can't tell whether you've got it or not …

why will there always be two left over?