Results 1 to 2 of 2

Math Help - Covering a square

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    26

    Covering a square

    Is it possible to remove one square from a 5 5 board so
    that the remaining 24 squares can be covered by eight 3 1
    rectangles? If yes, find all such squares
    (Hint: A domino is a 2 1 rectangle. As you may know,
    if two diagonally opposite squares of an ordinary 8 8
    chessboard are removed, the remaining 62 squares cannot
    be covered by 31 non-overlapping dominos. The reason
    being, after removing the two corners 32 squares of one
    colour and 30 of the other are left. No matter how you place
    a domino it will cover one white and one black square.)


    I found that if the central square is removed, the remaining squares can be covered. I don't think there are any other squares which apply.
    How do you show that you cannot cover the board if you remove any other square?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Quote Originally Posted by nahduma View Post
    Is it possible to remove one square from a 5 5 board so
    that the remaining 24 squares can be covered by eight 3 1
    rectangles? If yes, find all such squares
    (Hint: A domino is a 2 1 rectangle. As you may know,
    if two diagonally opposite squares of an ordinary 8 8
    chessboard are removed, the remaining 62 squares cannot
    be covered by 31 non-overlapping dominos. The reason
    being, after removing the two corners 32 squares of one
    colour and 30 of the other are left. No matter how you place
    a domino it will cover one white and one black square.)


    I found that if the central square is removed, the remaining squares can be covered. I don't think there are any other squares which apply.
    How do you show that you cannot cover the board if you remove any other square?
    You can color the board using 3 colors as follows:
    ABCAB
    BCABC
    CABCA
    ABCAB
    BCABC

    We have 8 A's, 9 B's and 8 C's.

    If you notice that each trimino covers exactly one A, one B and one C, you can see immediately that you have to omit a square colored by color B.

    Now, we can repeat the same reasoning with a different coloring (obtained using vertical symmetry):
    BACBA
    CBACB
    ACBAC
    BACBA
    CBACB

    There's only one square which has the color B in both colorings.

    You can easily find more similar problems, if you're interested in them, if you google for keywords like invariant, domino, chessboard
    Google
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. covering spaces
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: July 18th 2011, 04:56 PM
  2. Fixed radius disjoint ball covering vs. open covering
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: November 22nd 2010, 07:01 AM
  3. Covering Spaces
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 28th 2009, 11:17 AM
  4. Covering space
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: June 30th 2009, 07:22 AM
  5. covering
    Posted in the Calculus Forum
    Replies: 2
    Last Post: July 11th 2008, 01:01 PM

Search Tags


/mathhelpforum @mathhelpforum