3
$\begingroup$

Let's assume we put 8 rooks on a chess board but we are not allowed to place them on the main diagonal with the white squares. In how many ways can I arrange them so that they cannot attack each other.

My approach is:

You can put the first rook in 8 different rows of the chess board and you can combine them with 7 columns. The second rook can be placed in 7 different rows and you can choose out of 6 columns and so on. This leads to $8!7!$ different possibilities. You then have to eliminate $8!$-many possibilities as the rooks are not distinguishable. So I get $7!$ possibilities.

I think this must be wrong although the reasoning seems legit to me?!

Where is my mistake?

$\endgroup$
  • 1
    $\begingroup$ The question asks for the number of derangements of $\left\{1,2,\ldots,8\right\}$. You can easily find correct solutions to it. As for yours, I'm afraid I don't understand how it goes, so I cannot say where it goes wrong... $\endgroup$ – darij grinberg Nov 25 '19 at 23:37
  • $\begingroup$ What happened when you tried your method on a $4\times4$ chessboard and compared your answer with the actual count? $\endgroup$ – bof Nov 25 '19 at 23:59
1
$\begingroup$

The flaw in the reasoning is because you write "the second rook can be placed in $7$ different rows and you can choose $6$ different columns and so on" which is not actually correct - and should stand out as a red flag because no justification is given to a pretty non-obvious and important fact in your argument. Also, your "and so on" hides what happens to the last rook in your argument, which you would say can be put into $1$ row and $0$ columns - which is clearly wrong!

Suppose we put the coordinates on the grid ranging from $(1,1)$ to $(8,8)$ where the diagonal in question is those points of the form $(n,n)$. If you put the first rook at $(1,2)$, your claim is that there are $42$ valid positions for the second rook - but this is not so! More specifically, you claim that we can fix the first coordinate in $7$ ways and then will have $6$ choices for the second coordinate - but this does not hold. In particular, if we choose the first coordinate for the second rook to be $2$, we find that all positions $(2,x)$ are legal except for $(2,2)$ - which is both attacked by the the first rook and on the main diagonal. Oops - so there are actually $43$ valid positions for the second rook!

Patching this argument turns out to be really hard because the number of valid positions for the next rook will, in general, depend on the placement of the previous rooks - so finding another approach is warranted. (For instance, one can count the number of arrangements of rooks that do include the diagonal and also the total number of arrangements of rooks, then subtract. It's also to get a recurrence relation by considering that each square on the diagonal is attacked by two rooks - which then means you have some sort of relation on the rooks which is useful to counting the number of possible placements)

| cite | improve this answer | |
$\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.