Problem: 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 let $m$ be the median of $\left\{a_1, a_2, a_3\right\}$. Let $Q$ be the number of arrangements for which $m=5$. Find the remainder when $Q$ is divided by 1000 . Solution: Notice that if we have the median of $\{ a_{1},a_{2},a_{3} \}$ be $5$, then $5$ must literally show up as one of $a_{1},a_{2},a_{3}$ and the other two must sandwich $5$ (meaning one is below, and one is above). We reason similarly about the rows of the grid. In the row that will have median $5$, we must have that there is a number in the row in $\{ 1,2,3,4 \}$ and a number in the row in $\{ 6,7,8,9 \}$ (otherwise the median of this row would not be $5$). There are hence $4^2 3!$ ways to create a row with median $5$. Now, check this out. Once we've done this, notice it is IMPOSSIBLE for the other two rows to have a median strictly above $5$ or strictly below $5$ (as this would imply there are more than $3$ numbers greater than $5$ to distribute after selecting the row with median 5, or vis versa). In other words, if the two other rows had median gt; 5$, then we'd need to use at least $2$ numbers from $\{ 6,7,8,9 \}$ (that is not in the median-5 row) and one value from $\{ 1,2,3,4 \}$ (that is not in the median-5 row) to create a row of median gt; 5$, but when we go to do that again, we only have $1$ value left in $\{ 6,7,8,9 \}$ and two values in $\{ 1,2,3,4 \}$ which forces the median to be lt; 5$. The same thing happens if we try to construct two rows with median lt; 5$. That is to say, once we've picked the numbers to go in our median-5 row, there are $3$ rows we can make the median-5 row and we simply arrange the rest of the $6$ numbers in $6!$ ways. Hence, the solution is $4^{2}3! \cdot 3 \cdot 6! \pmod{1000} = 360$.