# Checkerboard problem

1. Feb 26, 2010

### morbius27

1. The problem statement, all variables and given/known data
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.

2. Feb 26, 2010

### tiny-tim

Hi morbius27!

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

3. Feb 26, 2010

### morbius27

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?

4. Feb 26, 2010

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

5. Feb 26, 2010

### morbius27

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?

6. Feb 26, 2010

### tiny-tim

What's 15 times ±2 ?

7. Feb 26, 2010

### morbius27

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?

8. Feb 26, 2010

### tiny-tim

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

why will there always be two left over?