Help in a mathematical induction problem involving a chess board.

402 Views Asked by At

We are given a chess game desk and some identical L-shaped figures each of which can cover exactly three fields on the desk (see the figure attached). enter image description here

1) Can the desk be fully covered by the figures, i.e., the figures are placed so that each field is under one figure only?

2) We have the right to remove an arbitrary field on the desk (such as the gray field on the right). Can the remaining part of the desk be fully covered by the figures?

1

There are 1 best solutions below

0
On BEST ANSWER

The answer to the first part of the question is no because $64$ is not divided by 3.

As for the second part the answer is yes and here's an algorithm to fill the chess board with the L shaped pieces:

Firstly split the chess board into $4$ squares of size $4*4$. The 3 squares that do not contain the gray square form a bigger "L". This "L" can be filled with 4 smaller "Ls" like in this image:enter image description here

Now each of the 4 smaller "Ls" can be filled with 4 smaller "Ls" each one consisting of 3 squares.

Repeat the same method for the $4*4$ square that contains the grey field, then repeat it for the $2*2$ square that remains and you will have filled the chessboard with the L shaped figures.

This works for any $2^n*2^n$ chessboard (it can be proved with induction).