Question

Beatrix is going to place six rooks on a $6 \times 6$ chessboard where both the rows and columns are labeled $1$ to $6;$ the rooks are placed so that no two rooks are in the same row or the same column. The value of a square is the sum of its row number and column number. The score of an arrangement of rooks is the least value of any occupied square. The average score over all valid configurations is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

Answer

Answer: 371

Concepts:expected value permutations arrangements with restrictions

Difficulty rating: 3160

Solution:

There are $6! = 720$ arrangements, and every score lies between $2$ and $7.$ Let $b_n$ be the number of arrangements with score at least $n.$ Since each score $s$ satisfies $s = 2 + \#\{n \ge 3 : s \ge n\},$ the total of all $720$ scores is $2 \cdot 720 + b_3 + b_4 + b_5 + b_6 + b_7.$

Score $\ge n$ means no rook occupies a square with row + column $\lt n.$ Place the rooks row by row. For $b_3,$ only $(1,1)$ is banned: $5 \cdot 5! = 600.$ For $b_4,$ row $1$ has $4$ allowed columns, then row $2$ has $4$ (column $1$ and the used column are excluded): $4 \cdot 4 \cdot 4! = 384.$ Similarly $b_5 = 3 \cdot 3 \cdot 3 \cdot 3! = 162,$ $b_6 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2! = 32,$ and $b_7 = 1$ (all rooks on the anti-diagonal).

The total is $1440 + 600 + 384$ $+ 162 + 32 + 1 = 2619,$ so the average is $\frac{2619}{720} = \frac{291}{80},$ and $p + q = 291 + 80 = 371.$

2016 AIME II Problem 13

Answer: 371

Difficulty rating: 3160

Solution:

Problem 13 in Other Years