Results 1 to 6 of 6

Math Help - Chess Board Proof

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Chess Board Proof

    a) Prove that if a perfect cover has no fault-lines, where m, n are even, then 2n + 2m - 4 <= mn/2.

    b)Prove that if a perfect cover has no fault-lines, where m is even and n is odd, then 2n+ (3/2)m - 4 <= mn/2.

    Can someone show one of these, so I can get an idea on how to do the other. Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    I think you will get a quicker answer if you will first define "perfect cover" and "fault line".
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2008
    Posts
    535
    Perfect cover = being able to completely cover a chess boards with dominoes with overlapping any of the dominoes
    Fault line = A "fault" in a perfect cover. THis means being able to cut the board in such a way that you don't cut, break, move, etc any of the dominoes
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    And what are m and n in your original problem statement?
    Last edited by awkward; February 2nd 2011 at 07:32 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Feb 2008
    Posts
    535
    Sorry. We are considering an mxn chessboard. m rows and n columns
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Here is a sketch of a proof for a), where m and n are even. (I suppose you have probably seen the beautiful proof of the case m=n=6. This is just a slight generalization.)

    Assume that a fault-free tiling exists. Then

    1. The area of the board is mn square units, so (1/2)mn dominoes are required to cover it.

    2. Can a possible fault line be blocked by a single domino? The answer is no, because the board excluding the domino is split into two regions by the fault line. Again excluding the single domino, the area of each region is an odd integer, and such a region cannot be covered by dominoes. Therefore each possible fault line must be blocked by at least two dominoes.

    3. A single domino can block at most one fault line.

    4. There are m-1 horizontal fault lines possible and n-1 vertical fault lines possible, for a total of m+n-2 possible fault lines. Combined with 2., we see that at least 2(m+n-2) dominoes are required to block all the possible fault lines.

    5. Combining 1. and 4.,
    (1/2)mn >= 2(m+n-2).

    One of the steps above is incorrect when one of the sides of the rectangle has an odd length. I leave it to you to figure out which step it is and how to revise the proof accordingly.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. chess problem
    Posted in the Statistics Forum
    Replies: 0
    Last Post: August 4th 2011, 05:52 PM
  2. Chess board and 2x1 domino stones.
    Posted in the Math Puzzles Forum
    Replies: 0
    Last Post: July 27th 2011, 05:09 PM
  3. knight on the chess board
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 15th 2011, 12:37 PM
  4. Grains of rice on a chess board
    Posted in the Math Puzzles Forum
    Replies: 8
    Last Post: March 10th 2010, 03:33 PM
  5. chess exercise
    Posted in the Statistics Forum
    Replies: 2
    Last Post: January 26th 2010, 03:14 PM

Search Tags


/mathhelpforum @mathhelpforum