Problem:
Beatrix is going to place six rooks on a chessboard where both the rows and columns are labeled to ; 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 , where and are relatively prime positive integers. Find .
Solution:
There are configurations. The minimum possible score of occurs when there is a rook on , and the maximum possible score of occurs when all the rooks are arranged on the squares for . Let be the number of configurations whose score is exactly , and let be the number of configurations whose score is at least . Then the total of all scores is
In each case the rooks are placed in row order; that is, a square is chosen in row , then a square in row , and so forth.
Because every configuration has a score of at least , conclude that . The configurations counted by do not have a rook in , so there are choices for where to put the first row's rook, and positions for the remaining rooks, showing that . The configurations counted by can have a rook in any of positions in row and a rook in any of positions in row , and there are positions for the remaining rooks, showing that ! . Using a similar line of reasoning, , and .
Then the total score is . The average is . The requested sum is .
The problems on this page are the property of the MAA's American Mathematics Competitions