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 triminoesif the square is not cut out from the center.

Can the result be generalised for any (2n+1)*(2n+1) chessboard?

HELP!

Printable View

- Aug 22nd 2010, 06:22 PMearthboyeasy 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! - Aug 22nd 2010, 06:50 PMundefined
- Aug 23rd 2010, 07:57 AMearthboysorry!
Very sorry!(Crying) for posting a wrong question.

i have edited my original post. - Aug 23rd 2010, 08:40 AMundefined
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.

- Aug 23rd 2010, 11:47 AMOpalg$\displaystyle \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. - Aug 23rd 2010, 12:59 PMemakarovQuote:

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

- Aug 23rd 2010, 01:09 PMundefined
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.