Difference between revisions of "2016 AIME II Problems/Problem 13"
(Solution) |
Mathgeek2006 (talk | contribs) m |
||
| Line 5: | Line 5: | ||
Solution by Shaddoll | Solution by Shaddoll | ||
| + | |||
| + | == See also == | ||
| + | {{AIME box|year=2016|n=II|num-b=12|num-a=14}} | ||
| + | {{MAA Notice}} | ||
Revision as of 09:16, 17 May 2016
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. 
