Results 1 to 7 of 7

Math Help - easy chessboard problem

  1. #1
    Member
    Joined
    Feb 2010
    From
    in the 4th dimension....
    Posts
    122
    Thanks
    9

    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!
    Last edited by earthboy; August 23rd 2010 at 08:04 AM. Reason: original question was wrong
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by earthboy View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Feb 2010
    From
    in the 4th dimension....
    Posts
    122
    Thanks
    9

    sorry!

    Very sorry! for posting a wrong question.
    i have edited my original post.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by earthboy View Post
    Very sorry! 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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    \setlength{\unitlength}{5mm}<br />
\begin{picture}(10,10)<br />
\thicklines<br />
\multiput(0,0)(0,2){6}{\line(1,0){10}}<br />
\multiput(0,0)(2,0){6}{\line(0,1){10}}<br />
\put(0.75,8.75){$R$}<br />
\multiput(2.75,8.75)(-2,-2){2}{$G$}<br />
\multiput(4.75,8.75)(-2,-2){3}{$B$}<br />
\multiput(6.75,8.75)(-2,-2){4}{$R$}<br />
\multiput(8.75,8.75)(-2,-2){5}{$G$}<br />
\multiput(8.75,6.75)(-2,-2){4}{$B$}<br />
\multiput(8.75,4.75)(-2,-2){3}{$R$}<br />
\multiput(8.75,2.75)(-2,-2){2}{$G$}<br />
\put(8.75,0.75){$B$}<br />
\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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chessboard problem. Olympiad question.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 10th 2012, 08:16 AM
  2. Chessboard problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 31st 2011, 03:47 PM
  3. chessboard problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: January 5th 2011, 01:00 AM
  4. chessboard problem
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: January 24th 2009, 06:02 AM
  5. Chessboard Problem!
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: October 22nd 2006, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum