What is the probability that there are two knights that can attack each other on a 3*3 chess board if each square contains a knight with 1/2 probability?
The probability that there are two knights that can attack each other on a 3*3 chessboard…
chessboardprobability
Related Solutions
The knight can meet iff they start on a square of the same color. Each move each knight changes color, so if they start on different colors, they'll always be on different colors. And conversely, if they do start on the same color, any path from one knight to the other is even, so you can divide its length by 2.
First of all, here is the proof that you can put no more than $32$ non-attacking knights on a chessboard. You can pair up the squares of the board into $32$ pairs, where each pair is a knight's move apart, as shown below. Since you can place at most one knight in each pair, you can place at most $32$ knights.
Now, imagine placing a queen on some square in this same diagram, and then placing an X on every square attacked by the queen, as well as an X on the squares a knight's move away from the queen. No matter where you place the queen, at least $4$ of these pairs will have both of their squares X'ed out. Therefore, the number of knights you can place is reduced by at least four, so you cannot place more than $28$ knights.
For example, when the queen is placed at $\mathrm A1$, the lower left corner, then the pairs $\mathrm {A1-C2, A2-C1,B2-D1}$, and $\mathrm{A4-C3}$ are all X'ed out (the letter is the column, and the number is the row). It is not too hard to verify case by case that the queen always X's out at least $4$ of these pairs. In fact, as the queen moves closer to the center, she X's out more pairs.
Best Answer
"Knightwise" we have a circular graph with $8$ vertices, and on some of these vertices there is a knight. We have to compute the probability $p$ that two adjacent vertices are taken. There are $2^8=256$ equiprobable configurations, and we have to count the configurations containing at least one pair of taken adjacent vertices. These are the good configurations.
If there are two knights there are $8$ good configurations, if there are three knights there are $8\cdot 4+8=40$ good configurations, and if there are four knights all configurations except the two regular ones are good, making ${8\choose4}-2=68$ good configurations. All ${8\choose5}+\ldots+{8\choose8}=93$ configurations with $\geq5$ knights are good. Since there are $8+40+68+93=209$ good configurations we obtain $$p={209\over256}\ .$$