Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2016 AIME II Problems/Problem 13

Revision as of 19:59, 17 March 2016 by Shaddoll (talk | contribs) (Solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

Solution

We casework to find the number of ways to get each possible score. Note that the lowest possible score is $2$ and the highest possible score is $7$. Let the bijective function $f(x)=\{1,2,3,4,5,6\} \to \{1,2,3,4,5,6\}$ denote the row number of the rook for the corresponding column number. For a score of $2$, we must have $f(1)=1$, and we can arrange the rest of the function however we want, so there are $5!=120$ ways. For a score of $3$, we must have either $f(1)=2$ or $f(2)=1$, and we can arrange the rest of the rooks however we want, so by PIE the number of ways is $5!+5!-4!=216$. For a score of $4$, we must have $f(1)=3$, $f(2)=2$, or $f(3)=1$. If $f(1)=3$, we just don't want $f(2)=1$, if $f(2)=2$, we don't want $f(1)=1$, or if $f(3)=1$, we don't want $f(1)=2$, otherwise we can arrange the function however we like. If at least $2$ of the values rooks have a value of $4$, we can arange the rest of the rooks however we like, so there are $3(5!-4!)-3(4!)+3!=222$ by PIE. If the score is $5$, then we have either $f(4)=1$, $f(3)=2$, $f(2)=3$, or $f(1)=4$. If we have the first case, we don't want $f(2)=2$, $f(1)=2$, or $f(1)=3$, so by PIE the number of bad cases is $4!+4!-3!=42$. If we have the second case, then we don't want $f(2)=1$, $f(1)=1$, or $f(1)=3$, so similarly there are $42$ bad cases. Therefore, there are a total of $54$ good cases for each one. The number of ways to get $f(1)=1, f(1)=4$ is $4!-3!$ because we don't want $f(2)=2$, the number of ways to get $f(4)=1, f(2)=3$ is $4!-3!$ ways because we don't want $f(1)=2$, the number of ways to get $f(2)=3, f(3)=2$ is $4!-3!$ ways because we don't want $f(1)=1$, and the number of ways to get $f(1)=4, f(2)=3$ is $4!-3!$ ways because we don't want $f(3)=1$. The number of ways to get at least $3$ cases satisfied is $6! \cdot 4$ because we can arrange the remaining rooks however we like, and the number of ways to get all $4$ cases satisfied is $2!=2$ ways because we can arrange the remaining rooks however we like, so by PIE we have $54 \cdot 4-18 \cdot 6 + 6! \cdot 4-2!=130$ ways to get a score of $5$. The only way to get a score of $7$ is to have all the rooks run on the antidiagonal. Therefore, the number of ways to get a sum of $6$ is $6!-120-216-222-130-1=31$. Thus, the expected sum is $\dfrac{120 \cdot 2 + 216 \cdot 3 + 222 \cdot 4 + 130 \cdot 5 + 31 \cdot 6 + 1 \cdot 7}{720}= \dfrac{2619}{720}=\dfrac{291}{80}$, so the desired answer is $291+80=\boxed{371}$.

Solution by Shaddoll

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_13&oldid=77671"