# Prove or disprove a chessboard with diagonal corners removed, cannot be tiled with L shape pieces or size 2

I think this is impossible, but I don't know how to prove an integer solution doesn't exist for a given equation. Here's my approach:

First, observations: The removed tile will be of the same color. (as on a nxn checkboard, color goes diagonally)
Each 2x1 piece will cover 1 black tile and 2 white tiles, or the opposite

Therefore, WLOG, assume two black tiles have been removed on a nxn chessboard. We must find a integer solution to the following system:

$j(2b+w)+k(2w+b)=\lfloor\frac{n^2}{2}\rfloor w+(\lceil\frac{n^2}{2}\rceil-2)b$, where j,k are the number of respective piece used, and w,b are the number of respectively colored tiles.

Multiply by 2 to get rid of the ceil & floor, and equating coeff of b,w, we get:

w: $n^2=2(j+2k)$

b: $n^2-4=2(2j+k)$

Sub $k=\frac{n^2-4k}{2}-2j$ into equation b

We obtain the constraint: $n^2-6j-8=0$ must have integer solutions.

Wolfram says this is unsatisfiable, but how does one prove this?

-
Surely a 2x1 piece covers two tiles? –  Chris Eagle Nov 22 '12 at 20:53
Ah... I meant a tile with 2 tiles on the first row and 1 tile on the second row. How shall I express this? –  Sam Nov 22 '12 at 20:55

EDIT If you mean a $L$ shaped piece covering $3$ squares, then note that the number of squares on a $n \times n$ chess board is $n^2$. Once you remove any two squares, there are only $n^2-2$ squares. This need to be a multiple of $3$ if we want to cover with the $L$ shaped pieces, since if we use $k$ $L$ shaped tiles, the number of squares it will cover is $3k$. Hence, we need $n^2 -2 =3k$. However, $n^2 \equiv 0,1 \pmod{3}$. Hence, not possible.

Old question:

If the chessboard is of the form $(2n+1) \times (2n+1)$, the number of squares is odd. Once you remove the diagonally opposite squares, the number of squares left is again odd. Every tile covers $2$ squares. Hence, if we place $k$ tiles it will cover even number of squares $2k$, whereas we want to cover an odd number of squares. Hence not possible,

If you remove the diagonally opposite squares from a $2n \times 2n$ chess board and say both are black. You then have $2n^2$ white squares and $2n^2-2$ black squares. Every $2 \times 1$ tile covers a black and white square. If we use $k$ tiles, then we need $k = 2n^2$ to cover the white squares but to cover the black squares, we get $k=2n^2-2$. Hence, no solution.

-
Apologies, 2x1 means a L shaped piece. Hence my formulae. What happens in this case? –  Sam Nov 22 '12 at 20:58
Thank you very much, I've over complicated things. –  Sam Nov 22 '12 at 21:04

Each piece covers three squares of the chessboard. There are $n^2-2$ squares to cover. But $n^2-2$ is never a multiple of $3$.

-
This is so much simplier! I've totally over complicated it. –  Sam Nov 22 '12 at 21:02
@Sam: You can read more about L-tromino tiling of these sorts of chessboards here: public.coe.edu/~jwhite/f09/math%20cult%20tromino.f09.pdf –  Isaac Solomon Nov 22 '12 at 21:02
Wish I can accept both answers... but Marvis was here first so I will go with his. Thanks! –  Sam Nov 22 '12 at 21:03
@Sam You can of-course up-vote other answers. Accepting an answer is different from up-voting an answer. –  user17762 Nov 22 '12 at 21:07