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!
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!
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.
$\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.
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.By symmetry (or by considering the mirror image of the above colouring), only the centre square is eligible.
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.