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

891 Views Asked by At

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?

2

There are 2 best solutions below

2
On BEST ANSWER

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.

4
On

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