Competition problem — Combinatorics

Library / /670 of 740

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

On a $3 \times 3$ chessboard, each square contains a knight with $\frac{1}{2}$ probability. What is the probability that there are two knights that can attack each other? (In chess, a knight can attack any piece which is two squares away from it in a particular direction and one square away in a perpendicular direction.)

Solution

Solution:

Notice that a knight on the center square cannot attack any other square on the chessboard, so whether it contains a knight or not is irrelevant.

For ease of reference, we label the other eight squares as follows:

0	5	2
3	X	7
6	1	4

Notice that a knight in square

i

attacks both square

i+1

and

i-1

(where square numbers are reduced modulo 8). We now consider the number of ways such that no two knights attack each other.

- 0 knights: 1 way.
- 1 knights: 8 ways.
- 2 knights: $\binom{8}{2}-8=20$ ways.
- 3 knights: $8+8=16$ ways, where the two 8s represent the number of ways such that the "distances" between the knights (index-wise) are $2,2,4$ and $2,3,3$ respectively.
- 4 knights: 2 ways.

Therefore, out of $2^{8}=256$ ways, $1+8+20+16+2=47$ of them doesn't have a pair of attacking knights. Thus the answer is $\frac{256-47}{256}=\frac{209}{256}$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.