2
$\begingroup$

In how many ways can $9$ black and $9$ white rooks be placed on a $6 × 6$ chess board, so that no white rook can capture a black one? A rook can capture another piece if it is in the same rank (row) or the same file (column) as the other piece, with no other pieces between the two?

I was thinking of a $6×6$ matrix, but that option doesn't seem to help?

$\endgroup$
  • 1
    $\begingroup$ Please find a title that says something about your question. No need to mention combinatorics, the tags will do fine. $\endgroup$ – Marc van Leeuwen Feb 26 '15 at 9:10
3
$\begingroup$

You can always permute rows and columns, so if there is any solution, there is one for which the black rooks occupy some initial $k$ rows and $l$ columns. One must have $kl\geq9$ and $(6-k)(6-l)\geq9$, and some simple algebra will tell you that $k=l=3$ is the only solution to this. So one must count the number of ways to select $3$ rows and $3$ columns for the black rooks (the remainder being for white), and that number is $$ \binom 63^2=400. $$.

$\endgroup$
  • $\begingroup$ Thanks for letting me know that you could permute rows and columns. How my solution has evolved. That is why combinatorics is fun and challenging. $\endgroup$ – Satish Ramanathan Feb 26 '15 at 9:27
  • $\begingroup$ I'm not able to get why $kl>= 9 and (6-k)(6-l)>=9$. Can you please help ? $\endgroup$ – Srinivas K Feb 26 '15 at 9:35
  • $\begingroup$ That's because there must be at least $9$ places (for the black rooks) in the intersection of the first $k$ rows and the first $l$ columns, and also least $9$ places (for the white rooks) in the intersection of the remaining $6-k$ rows and the remaining $6-l$ columns. $\endgroup$ – Marc van Leeuwen Feb 26 '15 at 9:43
  • $\begingroup$ @SrinivasK Also, the "simple algebra" can be performed using $kl+(6-k)(6-l)-18=2(k-3)(l-3)$, whose left hand side must be${}\geq0$. $\endgroup$ – Marc van Leeuwen Feb 26 '15 at 9:50
1
$\begingroup$

If white rooks and black rooks are indistinguishable, See the configuration below and black and white could be interchanged. Srinivas pointed out that we could stack up in columns too. That put if white occupies three columns to the top, the remaining columns could be occupied by Black to the bottom. Number of ways, a set of three white could occupy 3 columns is ${6\choose3}$ to the top and the rest of the columns should be occipied by Black. The answer is $({6\choose3})^2$

Marc, Understood. You have the full credit.

enter image description here

$\endgroup$
  • $\begingroup$ we could interchange the columns here and it would still work ! $\endgroup$ – Srinivas K Feb 26 '15 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.