Maths Olympiad Prep

Library / /668 of 740

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

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

Solution

Solution:

Suppose the 3×33 \times 3 square is

ABC
DEF
GHI

We count the number of ways a board could have two knights attack each other using PIE. First notice that in any setup with two knights attack each other, the center square must be empty. Also, for any pair of knights that attack each other, one must be in a corner, and the other at the center of a nonadjacent side. There are 8258 \cdot 2^{5} ways for one pair of knights to attack each other.

Next, we count the number of ways two pairs of knights attack each other: up to symmetry, there are four cases:
- knights at AA, BB, GG, HH, and DD and EE empty;
- knights at AA, HH, FF, and BB, DD, EE empty;
- knights at AA, BB, HH, II, and DD, EE, FF empty;
- knights at AA, CC, HH, and DD, EE, FF empty.

For each of these cases, there are four symmetries, so there are a total of 4(23+23+22+23)4 \cdot (2^{3} + 2^{3} + 2^{2} + 2^{3}) ways to have two pairs of knights attack each other.

Next, there's only one way for three pairs of knights to attack each other, discounting symmetry: AA, BB, GG, HH, II have knights, and DD, EE, FF empty. Then there are 4224 \cdot 2 \cdot 2 ways for three knights to attack.

Finally, there is only one way for four knights to attack: knights at AA, BB, CC, GG, HH, II and empty squares at DD, EE, FF, for a total of 22 ways after counting symmetries.

Applying PIE, we get that the total number of boards with at least one pair of knights attacking each other is
8254(23+23+22+23)+4222=158 8 \cdot 2^{5} - 4 \cdot (2^{3} + 2^{3} + 2^{2} + 2^{3}) + 4 \cdot 2 \cdot 2 - 2 = 158
Then the probability the 3×33 \times 3 board has a pair of knights attacking each other is 15829=79256\frac{158}{2^{9}} = \frac{79}{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.