Question

Consider arrangements of the $9$ numbers $1, 2, 3, \ldots, 9$ in a $3 \times 3$ array. For each such arrangement, let $a_1,$ $a_2,$ and $a_3$ be the medians of the numbers in rows $1,$ $2,$ and $3,$ respectively, and then let $m$ be the median of $\{a_1, a_2, a_3\}.$ Let $Q$ be the number of arrangements for which $m = 5.$ Find the remainder when $Q$ is divided by $1000.$

Answer

Solution:

Rename each of $1, 2, 3, 4$ as L and each of $6, 7, 8, 9$ as G. If $5$ is not a row median, then no row median equals $5,$ so $m \neq 5.$ Thus $5$ 's row must contain one L and one G (reading L5G in some order), and the other two rows must supply one median below $5$ and one above. With the remaining three L's and three G's, those rows are either LLL and GGG, or LLG and LGG.

Count arrangements of letters: the three row types can be assigned to rows $1, 2, 3$ in $3! = 6$ ways, and the L5G row can be ordered in $3! = 6$ ways. In the first case LLL and GGG have $1$ ordering each, giving $6 \cdot 6 \cdot 1 = 36$ patterns; in the second, LLG and LGG each have $3$ orderings, giving $6 \cdot 6 \cdot 9 = 324$ patterns. That is $360$ letter patterns in all.

Finally the four L's can be filled with $1, 2, 3, 4$ in $4!$ ways and the four G's with $6, 7, 8, 9$ in $4!$ ways, so $Q = 360 \cdot 24^2 = 207360,$ whose remainder mod $1000$ is $360.$

2017 AIME I Problem 11

Solution:

Problem 11 in Other Years