Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a $6\times6$ chess board with $13$ marked squares, can you always place three mutually non-attacking rooks on the marked squares? If so, how can this be proven?

share|improve this question
    
You mean to say that there are three rooks which will never attack each other? –  Sawarnik Feb 22 at 5:26
    
Yes. Maybe at the end –  user130644 Feb 22 at 5:30
    
I think it should just say three pieces that occupy three different rows and three different columns. According to the rules of chess, two rooks even if on the same row or column (rank and file?) do not attack each other if there is a piece between, but this exception is not intended. (Also one usually glosses over the fact that rooks that attack each other have to be of opposite colours; if of the same colour they would instead defend each other.) –  Marc van Leeuwen Feb 22 at 7:47
    
If you randomly put 13 rooks on a 6x6 chess board prove that 3 of them will never attack each other". –  user130644 Feb 22 at 16:24

1 Answer 1

The squares of the board can be divided into six subsets, each one consisting of a NE-SW diagonal that wraps around the board if necessary. Mathematically, the $j$th subset ($0\le j\le5$) consists of those squares in the $r$th row and $c$th column such that $r-c\equiv j\pmod 6$. These subsets are pictured below.

Since there are 13 rooks and 6 such subsets, some subset must contain at least 3 rooks (by the pigeonhole principle). Those 3 rooks cannot attack one another.

enter image description here

(A similar argument with NW-SE diagonals shows that there must be at least two such subsets of 3 rooks, which overlap in at most 1 rook.)

share|improve this answer
    
+1 for finding (IMHO) A) a very plausible interpretation that made the question interesting, B) a solution that makes it unnecessary to interpret whether two rooks on the same row/file attack each other, if there is a third rook between them. –  Jyrki Lahtonen Feb 22 at 7:43
    
Interesting. But.. What is the meaning of "jTH", rTH, cth. Why r-c=j? –  user130644 Feb 22 at 16:27
    
I don't understand... The subsets are rectangles of 3x2? Or how –  user130644 Feb 22 at 16:38
    
+1 nice visual solution. –  mjqxxxx Feb 22 at 18:15
    
Thank you very much! –  user130644 Feb 23 at 6:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.