easy chessboard problem

Printable View

August 22nd 2010, 06:22 PM
earthboy

easy chessboard problem

A 5*5 chessboard is given.A square is cut from the board.Show that it is not possible to cover the rest of the board by 3*1 triminoes if the square is not cut out from the center.
Can the result be generalised for any (2n+1)*(2n+1) chessboard?
HELP!
August 22nd 2010, 06:50 PM
undefined

Quote:

Originally Posted by earthboy

A 5*5 chessboard is given.A square is cut from the board.Show that it is possible to cover the rest of the board by 3*1 triminoes .

This is not true, or perhaps the wording is bad. If the center square is removed then the tiling is possible. But if a corner square is removed then a tiling is not possible.
August 23rd 2010, 07:57 AM
earthboy

sorry!

Very sorry!(Crying) for posting a wrong question.
i have edited my original post.
August 23rd 2010, 08:40 AM
undefined

Quote:

Originally Posted by earthboy

Very sorry!(Crying) for posting a wrong question.
i have edited my original post.

Assuming the question is now right, it is not hard to solve the 5x5 case by exhaustive enumeration and in fact won't take long to write on paper. Accounting for symmetry there are only 5 squares that can be removed. Proving for a corner square was simple because once you fix a single triomino, other triomino placements become necessary and the end result is an impossibility (try it if you like). Of course this is not very elegant and won't scale to larger board sizes. So presumably a nicer proof exists.
August 23rd 2010, 11:47 AM
Opalg

$\setlength{\unitlength}{5mm} \begin{picture}(10,10) \thicklines \multiput(0,0)(0,2){6}{\line(1,0){10}} \multiput(0,0)(2,0){6}{\line(0,1){10}} \put(0.75,8.75){$R$} \multiput(2.75,8.75)(-2,-2){2}{$G$} \multiput(4.75,8.75)(-2,-2){3}{$B$} \multiput(6.75,8.75)(-2,-2){4}{$R$} \multiput(8.75,8.75)(-2,-2){5}{$G$} \multiput(8.75,6.75)(-2,-2){4}{$B$} \multiput(8.75,4.75)(-2,-2){3}{$R$} \multiput(8.75,2.75)(-2,-2){2}{$G$} \put(8.75,0.75){$B$} \end{picture}$

Colour each square of the 5x5 board Red, Green or Blue as indicated in the diagram. There are 8 red, 8 blue and 9 green squares. Each triomino covers one square of each colour, so the square that is cut out has to be a green one. By symmetry (or by considering the mirror image of the above colouring), only the centre square is eligible.

Hopefully that idea will help you to investigate the (2n+1)x(2n+1) case also.
August 23rd 2010, 12:59 PM
emakarov

Quote:

By symmetry (or by considering the mirror image of the above colouring), only the centre square is eligible.

Let's see if I understand this right. The mirror image (vertical or horizontal) maps a trimino-filled board into another trimino-filled board. However, the image of a green square is not green unless it is the central square. Therefore, if one has a filled board where a non-central green square is cut out, then one gets a similar board where a non-green square is cut out, which is impossible.
August 23rd 2010, 01:09 PM
undefined

Quote:

Originally Posted by emakarov

Let's see if I understand this right. The mirror image (vertical or horizontal) maps a trimino-filled board into another trimino-filled board. However, the image of a green square is not green unless it is the central square. Therefore, if one has a filled board where a non-central green square is cut out, then one gets a similar board where a non-green square is cut out, which is impossible.

I think it's simpler than that. Consider the cell in row 1, column 2. In the original diagram, it is green and can potentially be removed. But in the mirror image, it is not green and cannot be removed. Since there exists a colouring such that the cell cannot be removed, it cannot be removed in general.