Results 1 to 2 of 2

Math Help - Rooks on a checkboard

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    91

    Rooks on a checkboard

    For every n\geq 2, determine the greatest number of rooks that can be placed on a n\times n checkerboard so that the following property is satisfied: if a rook is attacked by two others, then all three are on the same line.
    Last edited by atreyyu; April 30th 2010 at 02:45 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by atreyyu View Post
    For every n\geq 2, determine the greatest number of rooks that can be placed on a n\times n checkerboard so that the following property is satisfied: if a rook is attacked by two others, then all three are on the same line.
    I will outline a solution with some parts left for you to fill in.

    The number of rooks that can be placed is 2n-2. We need to show, first, that 2n-2 rooks can be placed on an n by n chessboard subject to the required constraint; second, that no larger number can be placed. I leave the first part to you.

    To show that no more than 2n-2 rooks can be placed, assume the contrary; i.e., for some n, more than 2n-2 rooks can be placed on an n by n chessboard such that no rook shares a row and column with two other rooks. Choose the least such n. It is clear that we can't place more than 2 rooks on a 2 by 2 chessboard without violating the constraint, so n is greater than 2.

    Suppose we have our rooks on the chessboard-- i.e., consider a suitable configuration of more than 2n-2 rooks.

    We claim that some row has at most 1 rook in it. If not, there must be at least 2 rooks in every row. Each such 2 rooks eliminate 2 columns from the places where we can place rooks, so there are 2n columns where we can't place a rook. This can't be, since there are only n columns. So, as claimed, there is a row with at most 1 rook in it-- say row i.

    Similarly, there is a column with at most 1 rook in it, say column j. Remove row i and column j from the chessboard. What remains is an n-1 by n-1 chessboard with at least 2n-1-2 = 2(n-1)-1 rooks, such that if any rook is attacked by 2 others, then all 3 are on the same row or column. Since 2(n-1)-1 > 2(n-1)-2, this violates our assumption that n is minimal. This contradiction shows that no such configuration is possible.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. how many ways can rooks be placed?.
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 12th 2009, 04:45 AM

Search Tags


/mathhelpforum @mathhelpforum