9
$\begingroup$

The Problem:-

"In chess, a rook attacks any piece in the same row or column as the rook, provided no other piece is between them. In how many ways can $8$ rooks be placed on a $[8\times8]$ chessboard so that no two attack each other? What about $8$ rooks on a $10\times10$ board?"

I believe I have an answer for the first part of the question. When placing the first rook, there are 8 places on any particular column (or row) to place the rook, leaving just 7 places on a different column (or row) for the next rook, and so on, providing 8! possible ways to place the rooks in such a way that they cannot attack each other ($P(8,8) = 8!/(8-8)! = 8!$).
However, I am not sure I fully understand how this would work for a board where there are more rows and columns than pieces (such as on a 10x10 board). Does it become $P(10,8) = 10!/(10-8)! = 10!/2$ ? If so, why? If not, how should I approach this problem?

This problem was found in "Introduction to Combinatorics and Graph Theory" by David Guichard.

$\endgroup$
  • 5
    $\begingroup$ Only one rook can go on each row and on each column. If there are two more rows and columns there are two rows and two columns with no rooks on them. just declare at the begininning that there will be 2 rows which won't be used. There are ${10 \choose 2}$ ways of doing that and ${10 \choose 2}$ ways of choosing the columns. So there are ${10\choose 2}^2 *D$ ways of doing this if $D$ is the number of ways to do it on an 8x8 board. $\endgroup$ – fleablood Nov 7 '17 at 18:45
9
$\begingroup$

So for the first question you need to place a rook in each column. The rook in the first column can go in $8$ places, the rook in the second column then has $7$ possible rows etc.

In the second part, you need first to choose the $8$ columns out of the $10$ available, and then place a rook in each of the columns. If once again you move from left to right, counting the number of possibilities, you should be fine.

Rather than talking about "any particular" column or row, you should make a habit of defining the scheme more closely (the first, second rather than "any" etc). This will help to avoid a great deal of confusion and can also highlight any double-counting.

$\endgroup$
  • $\begingroup$ For clarification, to determine the number of possible combinations for placing 8 rooks on a 10x10 board, we could calculate 10 choose 8 to determine how many 8x8 boards we could have, and then use that to determine how many total combinations there are, by multiplying the number from 10 choose 8 (45) with the number of possible permutations on the board (8!)? $\endgroup$ – oath Nov 7 '17 at 18:54
  • 1
    $\begingroup$ @oath With $\binom {10}{8}$ columns you effectively reduce to a $10\times 8$ board - but then you have to find a position in each column (there are ten positions to start with, and each choice reduces the possibilities for the next choice by one) $\endgroup$ – Mark Bennet Nov 7 '17 at 18:56
  • $\begingroup$ Ooooh, I see. So with this line of thought, would $10\choose 8$ multiplied by permutations $P(10,8)$ give the correct answer ($10\choose 8$ gives 45, and the permutation $P(10,8)$ gives $10!/2!$) (the answer provided by @Bram28)? $\endgroup$ – oath Nov 7 '17 at 19:15
4
$\begingroup$

For the second part, if we first focus on the columns the rooks are in: since there cannot be two rooks in the same column, the rooks must appear in $8$ different columns. And you can choose $8$ columns out of $10$ in

$$10 \choose 8$$

ways. Once, we've chosen the $8$ columns, let's place the rooks in those columns. Well, you can place the first rook in $10$ different rows, the next in $9$, etc. until the last one, which can be place in $3$ different rows, so we can place those $8$ rooks in:

$$\frac{10!}{2!} = \frac{10!}{2}$$

ways. This leads to a grand total of:

$${10 \choose 8} \cdot \frac{10!}{2}$$

ways of placing $8$ rooks on a $10 \times 10$ board.

$\endgroup$
  • 3
    $\begingroup$ As a variation on this, we can (independently) choose eight columns and eight rows to be populated, each in $$ 10 \choose 8 $$ different ways. Having done that, the chosen rows and columns form a board equivalent to the 8 x 8 case, which the OP has already answered (8!). Overall, then, for 10 x 10 case, there are $$ {10 \choose 8} ^ 2 \cdot 8! $$ different ways to place the 8 rooks. $\endgroup$ – John Bollinger Nov 7 '17 at 22:20
  • $\begingroup$ @JohnBollinger Ooh, nice, thanks! $\endgroup$ – Bram28 Nov 7 '17 at 22:25
2
$\begingroup$

This is a different approach than what's been offered so far, but that might help some people understand the problem differently.

I would solve this by first assuming order mattered when placing the rooks (so placing on $A1$ then $B2$ is different than $B2$ then $A1$), then adjusting my answer to compensate.

The number of squares you can place the first rook on is $10^2$. Wherever you place it, you effectively turn your board into a $9 \times 9$ board with no rooks on it.

Now that we've lost a row and a column from our first rook, the number of squares you can place the second rook on is $9^2$.

Carrying on for each rook, we get:

$$10^2 \cdot 9^2 \cdot ... \cdot 3^2$$

Ways to place our rooks (don't forget we only have $8$ rooks, so we don't go all the way to $1^2$). Remember though, we assumed order matters. In reality, it does not. However, there's only $8!$ different ways to order our rooks, so we can divide our initial answer by $8!$, leaving:

$$ (10^2 \cdot 9^2 \cdot ... \cdot 3^2) / 8!$$

Ways to place our rooks.

$\endgroup$
1
$\begingroup$

For the first case of placing 8 rooks on an 8x8 board your result of 8! is correct.

For the second case of placing 8 rooks on a 10x10 board I find the following approach to be the simplest way to do the calculations:

There are 10*9/2 = 45 ways to choose which two rows you will not be using. Likewise there are 45 ways to choose which two columns you will not be using.

Once you have chosen which rows and columns not to use there are 8! ways to place the rooks in the remaining squares.

That gives a total of 8!*45² = 81648000 possibilities.

$\endgroup$

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.