2016 AIME II Problems/Problem 13
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 of a square is the sum of its row number and column number. The 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
We casework to find the number of ways to get each possible score. Note that the lowest possible score is and the highest possible score is . Let the bijective function denote the row number of the rook for the corresponding column number. For a score of , we must have , and we can arrange the rest of the function however we want, so there are ways. For a score of , we must have either or , and we can arrange the rest of the rooks however we want, so by PIE the number of ways is . For a score of , we must have , , or . If , we just don't want , if , we don't want , or if , we don't want , otherwise we can arrange the function however we like. If at least of the values rooks have a value of , we can arange the rest of the rooks however we like, so there are by PIE. If the score is , then we have either , , , or . If we have the first case, we don't want , , or , so by PIE the number of bad cases is . If we have the second case, then we don't want , , or , so similarly there are bad cases. Therefore, there are a total of good cases for each one. The number of ways to get is because we don't want , the number of ways to get is ways because we don't want , the number of ways to get is ways because we don't want , and the number of ways to get is ways because we don't want . The number of ways to get at least cases satisfied is because we can arrange the remaining rooks however we like, and the number of ways to get all cases satisfied is ways because we can arrange the remaining rooks however we like, so by PIE we have ways to get a score of . The only way to get a score of is to have all the rooks run on the antidiagonal. Therefore, the number of ways to get a sum of is . Thus, the expected sum is , so the desired answer is .
Solution by Shaddoll
See also
2016 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.