On a regular chess board (8 by 8 possible positions) we place 8 towers. How many possibilities are there where no tower can beat another tower, i.e no more than one tower on each row and and column.
This is for example an allowed configuration:
The correct answer is 8!, and the expiation goes something like:
Chose a certain row. On this row, we have 8 possible allowed choices for the first piece. On the next row, we have 7 possible positions. Etc, down to the last row.
However, I don't really understand why my way of thinking is incorrect. I was thinking that for the first piece, we have 8*8 allowed positions. For the next one, the first piece have "tainted" an entire row and column, allowing us 7*7choices, etc. This, of course, give us many more choices.
I have a gut feeling that it's wrong, but I can't really tell why.
Any suggestions?
$\endgroup$ 31 Answer
$\begingroup$Well, we can have at most one rook per row. There are eight rows. In the first row, we can place a rook anywhere -- that's eight choices. In the next row, there are seven choices, because the rook we just placed removes one column. In the next row, there are six choices, because two columns are blocked. In the next row, we have five choices... and the total number of configurations will be $8 \times 7 \times 6 \ldots = 8!$.
Now to the interesting question: why is it not $8^2 \times 7^2 \times 6^2 \ldots \times 1^2$? Well, it kind of is. This does give us all the possible ways to place the towers on the chessboard. However, if you look carefully, you'll see that you're over-counting: you are implicitly distinguishing (labeling) the rooks. You need to divide this result by the total number of ways to label the rooks, which is $8!$. So the result is: $$\frac{8^2 \times 7^2 \times 6^2 \times \ldots \times 1^2}{8!}$$ $$= \frac{8 \times 8 \times 7 \times 7 \times 6 \times 6 \ldots \times 1}{8\times 7 \times 6 \times 5 \times \ldots \times 1}$$ $$= 8\times 7 \times 6 \times 5 \times \ldots \times 1$$ $$=8!$$
Finally, note that this question has been asked before on this site, e.g. here. I've voted to close this question.
$\endgroup$ 2
