3

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: 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?

Filip Nilsson
  • 111
  • 1
    Hint: Can you tell the towers apart from each other? – Scortchi - Reinstate Monica Jan 09 '15 at 17:21
  • 1
    Please do the problem very carefully for a 2 by 2 board, then for a 3 by 3 board. – Will Jagy Jan 09 '15 at 18:18
  • Your method counts some arrangements more than once. Following Will Jagy's suggestion, consider a $2\times2$ board. Suppose you put the first rook at a1 and the second at b2. Now suppose you put the first rook at b2 and the second at a1. Your method counts these separately, as 2 arrangements, but they are the same, and should be counted only once. To see how to use your method to get the right answer, see this post. – MJD Jan 09 '15 at 19:37

1 Answers1

3

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.

Community
  • 1
Newb
  • 17,672
  • 13
  • 67
  • 114