2
$\begingroup$

The problem goes as follows:

Eight rooks are randomly placed in distinct squares of 8x8 chess-board. Find the probability that all the rooks are safe from one another, i.e., that there is no row or column with more than one rook.

I know what is the solution. Many people on the Internet explained this problem, but all of them did it in the same way, so I could not find an answer to my question.

All solutions agree that required probability is equal to $\frac{64 \times 49 \times 36 \times 25 \times 16 \times 9 \times 4}{\frac{64!}{56!}}$. The first time I was solving this problem, I got $\frac{64 \times 49 \times 36 \times 25 \times 16 \times 9 \times 4}{{64 \choose 8}}$, so the difference is that I do not have $8!$ in denominator. The reason why I missed to multiply denominator by $8!$ is because I thought it was enough to find the number of combinations ${64 \choose 8}$ and that order in these combinations was not important. In fact, I think this is true if all of the rooks are the same (non-distinguishable).

I think the problem is in the problem statement, it does not say if the rooks are different or not. Can anyone tell me what would be results for these two cases: 1) with non-distinguishable rooks, 2) with the same rooks?

$\endgroup$
  • $\begingroup$ two cases are the same in your question, did you mean 1) with distinguishable rooks, 2) with the same rooks? $\endgroup$ – ArsenBerk Dec 21 '17 at 0:54
  • 2
    $\begingroup$ If you choose to use $\binom{64}{8}$ as your sample space size and use the sample space where the order in which the rooks are placed does not matter then that is perfectly fine and valid, however you will need to also take that into account when counting for your numerator too! A way to see the numerator in that case would be recognizing that every row gets exactly one and it must be in a column different than any previous selection. This gives $8\cdot 7\cdot 6\cdots 2\cdot 1=8!$ possibilities. (compare to $8^2\cdot 7^2\cdot 6^2\cdots 2^2=64\cdot 49\cdot 36\cdots 4$) $\endgroup$ – JMoravitz Dec 21 '17 at 0:59
  • 4
    $\begingroup$ This would give an answer of $\frac{8!}{\binom{64}{8}}$, the exact same answer as before, just written in a different way. $\endgroup$ – JMoravitz Dec 21 '17 at 0:59
  • $\begingroup$ The order does not matter. You can divide combinations by combinations, or you can divide permutations by permutations, and you will get the same answer either way. What is wrong is to divide permutations by combinations like you did in your wrong answer. $\endgroup$ – bof Dec 21 '17 at 1:01
  • 2
    $\begingroup$ As for the question of whether the rooks look the same or not, there is no difference in the final probability. Imagine that the rooks are distinguished by color. The rooks were placed randomly in the first place, and the placement could have been done by a blind person who is unable to tell the difference between them despite the fact that we can tell the difference between them but he can't. The probability that they can't attack eachother is the same whether the person placing them could see them to tell the difference or not. From math perspective, multiply top and bottom by $8!$. $\endgroup$ – JMoravitz Dec 21 '17 at 1:05
2
$\begingroup$

Collecting thoughts from comments above:

As with any probability problem, it is incredibly lenient what specific sample space to use when calculating. The standard requirement if we want to use counting methods to calculate the probability is for the sample space to be equiprobable, meaning that each outcome in the sample space be equally likely to occur. This is by no means necessary in general, but if we get this then we can use familiar rules like $Pr(A)=\dfrac{|A|}{|S|}$ which would otherwise not be allowed.

What specific choice for sample space that we use can be incredibly detailed, or heavily simplified. I will highlight three useful choices for our sample space and calculations related to each for our probability, as well as a fourth sample space which although perfectly valid will be incredibly tedious to work with and should not have been used for this specific problem. Generally, the simpler of a sample space we can work with, the easier our calculations will be but sometimes going too simplified will cause us to lose intuition.


Scenario 1: All rooks look the same and the order in which they are placed does not matter.

In this case, as the order in which the rooks are placed does not matter, we can describe any outcome of how they are placed as size-8 subsets of the set of $64$ available spaces. As such, there will be $\binom{64}{8}$ equally likely such subsets.

As the order in which the rooks are placed does not matter to us at the moment, we can describe every arrangement which satisfies the description "no rook can attack another" uniquely by which column the rook appears in for each row noting that a rook may not appear in a column previously selected for an earlier row. By multiplication principle, we get then $8\cdot 7\cdot 6\cdots 1=8!$ possible arrangements. This gives a final probability of $$\frac{8!}{\binom{64}{8}}$$


Scenario 2: Rooks look the same but order in which the rooks are placed matters.

In this case, as the order in which the locations in which rooks are placed are selected matter, we can describe any outcome of how they are placed as sequences of length-$8$ with no repeats with entries all taken from our set of $64$ available spaces. As such, there will be $64\cdot 63\cdot 62\cdots 57=\frac{64!}{56!}$ equally likely sequences.

Each arrangement which satisfies the description "no rook can attack another" can be described by a sequence of spaces selected such that no space selected can be attacked any any previous space. Each time we make such a selection, our available choices decreases. Originally there are $64$ choices. Having removed that and those spaces targettable from that space, there are $49$ remaining spaces, and then $36$ and so on, giving a total of $64\cdot 49\cdot 36\cdots 4\cdot 1=8^2\cdot 7^2\cdot 6^2\cdots 1^2=(8!)^2$ which yields a final probability of $$\frac{(8!)^2}{\frac{64!}{56!}}$$ which one should be able to quickly confirm equals the same answer as before.


Scenario 3: Rooks look different (e.g. by color), the order in which rooks are taken to be placed is randomized, and the order in which the rooks are placed matters as well.

This is to answer your question of "does it matter if rooks look the same or not." The end result is no. If we were to describe the set of outcomes, we could do so by describing it as a colored sequence of eight spaces from the board. Pick the location and the color for the first placed, then the location and the color for the second placed, and so on to get $64\cdot 8\cdot 63\cdot 7\cdot 62\cdot 6\cdots 57\cdot 1=\frac{64!}{56!}8!$

As in the previous case, we do the same with the exception of worryign about color now too, giving $64\cdot 8\cdot 49\cdot 7\cdot 36\cdot 6\cdots 4\cdot 2 \cdot 1\cdot 1=(8!)^3$. This would yield a final probability of$$\frac{(8!)^3}{\frac{64!}{56!}8!}$$ which again equals the same as before.


Scenario 4: Not only are rooks distinguishable by color, order of selection matters, but the person placing pieces will continue to place $56$ additional multicolored pawns after having placed all eight rooks. In this scenario, we would have a whopping $(64!)^2$ different outcomes in our sample space. The locations and colors of the pawns has literally nothing to do with whether or not the rooks share rows or columns (alternatively this is assuming that we say that pawns don't block movement to keep the spirit of the problem the same).

If we were to run with this scenario, not only will we need to account for rooks not sharing rows or columns, but we will need to account for how the rest of the pawns are placed too when calculating our numerator. Too much wasted effort.

$\endgroup$
2
$\begingroup$

Try $2$ rooks on a $2\times2$ chessboard:

  • Distinguishable: $4 \times 3 =\frac {4!}{2!} =12$ ways of placing the first and then the second rook, of which $4 \times 1=4$ are safe

  • Indistinguishable: ${4 \choose 2} =6$ ways of choosing two places from four, of which $\frac{2!^2}{2!}=2!=2$ patterns are safe

So clearly the probability is $\dfrac13$. This corresponds to $\dfrac{4}{\frac {4!}{2!}}$ and to $\dfrac{2!}{{4 \choose 2}}$ but not to $\dfrac{4}{{4 \choose 2}}$

Similarly with $8$ rooks on a $8\times8$ chessboard you can choose the distinguishable route $\dfrac{64\times 49 \times 36 \times 25 \times 16 \times 9 \times 4}{\frac {64!}{56!}} $ or the indistinguishable route $\dfrac{8!}{{64 \choose 8}}$, both being $\dfrac{(8!)^2 \times (8^2-8)!}{(8^2)!}$ but you cannot mix and match

$\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.