Question

Beatrix 要在一个 $6 \times 6$ 棋盘上放置六个车，棋盘的行和列都标为 $1$ 到 $6$ ；放置时任意两个车都不在同一行或同一列。一个格子的值定义为它的行号与列号之和。一种摆放的得分定义为所有被占格子中的最小值。所有合法摆放的平均得分为 $\frac{p}{q}$ ，其中 $p$ 与 $q$ 是互质的正整数。求 $p + q$ 。

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

答案

答案：371

知识点：期望值排列有限制的排列

难度评级：3160

解答：

共有 $6! = 720$ 种摆放，并且每个得分都在 $2$ 与 $7$ 之间。令 $b_n$ 为得分至少为 $n$ 的摆放数。因为每个得分 $s$ 满足 $s = 2 + \#\{n \ge 3 : s \ge n\}$ ，所以所有 $720$ 个得分的总和为 $2 \cdot 720 + b_3 + b_4 + b_5 + b_6 + b_7.$

得分 $\ge n$ 意味着没有车占据行号与列号之和 $\lt n$ 的格子。逐行放置。对 $b_3$ ，只有 $(1,1)$ 被禁用，共有 $5 \cdot 5! = 600$ 种。对 $b_4$ ，第 $1$ 行有 $4$ 个可用列，然后第 $2$ 行有 $4$ 个可用列（列 $1$ 和已使用列被排除），共有 $4 \cdot 4 \cdot 4! = 384$ 种。类似地， $b_5 = 3 \cdot 3 \cdot 3 \cdot 3! = 162$ ， $b_6 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2! = 32$ ，且 $b_7 = 1$ （所有车都在反对角线上）。

总和为 $1440 + 600 + 384$ $+ 162 + 32 + 1 = 2619$ ，所以平均值为 $\frac{2619}{720} = \frac{291}{80}$ ，从而 $p + q = 291 + 80 = 371$ 。

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 第 13 题

答案：371

难度评级：3160

解答：

其他年份的第 13 题