6 Consider a rectangular array of single digits $d_{i, j}$ with 10 rows and 7 columns, such that $d_{i+1, j}-d_{i, j}$ is always 1 or -9 for all $1 \leq i \leq 9$ and all $1 \leq j \leq 7$, as in the example below. For $1 \leq i \leq 10$, let $m_{i}$ be the median of $d_{i, 1}, \ldots, d_{i, 7}$. Determine the least and greatest possible values of the mean of $m_{1}, m_{2}, \ldots, m_{10}$.
Example:
\begin{tabular}{lcccccccc} 
& $d_{i, 1}$ & $d_{i, 2}$ & $d_{i, 3}$ & $d_{i, 4}$ & $d_{i, 5}$ & $d_{i, 6}$ & $d_{i, 7}$ & $m_{i}$ \\
$i=1$ & 2 & 7 & 5 & 9 & 5 & 8 & 6 & median is 6 \\
$i=2$ & 3 & 8 & 6 & 0 & 6 & 9 & 7 & median is 6 \\
$i=3$ & 4 & 9 & 7 & 1 & 7 & 0 & 8 & median is 7 \\
$i=4$ & 5 & 0 & 8 & 2 & 8 & 1 & 9 & median is 5 \\
$i=5$ & 6 & 1 & 9 & 3 & 9 & 2 & 0 & median is 3 \\
$i=6$ & 7 & 2 & 0 & 4 & 0 & 3 & 1 & median is 2 \\
$i=7$ & 8 & 3 & 1 & 5 & 1 & 4 & 2 & median is 3 \\
$i=8$ & 9 & 4 & 2 & 6 & 2 & 5 & 3 & median is 4 \\
$i=9$ & 0 & 5 & 3 & 7 & 3 & 6 & 4 & median is 4 \\
$i=10$ & 1 & 6 & 4 & 8 & 4 & 7 & 5 & median is 5
\end{tabular}
Solution 1: Note that rearranging the columns does not change the medians, hence we may sort the first row, so that $d_{1,1} \leq d_{1,2} \leq \ldots \leq d_{1,7}$. The calculations are much simplified if we subtract $i-1$ from each row. In other words, we put $D_{i, j}=d_{i, j}-(i-1)$. This subtracts $i-1$ from the median $m_{i}$ as well - that is if $M_{i}$ is the median of $D_{i, j} \mathrm{~s}$, then $M_{i}=m_{i}-(i-1)$. Thus the sum of the $M_{i} \mathrm{~s}$ is equal to the sum of the $m_{i} \mathrm{~s}$ minus $0+1+2+\ldots+9=45$. We shall show that sum of $M_{i}$ 's is 0 , so that the sum of the $m_{i} \mathrm{~s}$ is 45 and the average is always 4.5 .
Note that since $D_{1,1} \leq D_{1,2} \leq \ldots \leq D_{1,7}$ the entry $D_{1,4}$ is a median. The fourth column will continue to contain a median until $d_{i, 7}=0$ (at which point the third column will contain a median), that is $10-D_{1,7}$ times (note that $\left.d_{1,7}=D_{1,7}\right)$. The sum of those medians is then equal $D_{1,4}\left(10-D_{1,7}\right)$. After that, median moves to the third column and stays there until $d_{i, 6}=0$ (this may be no time at all, if $d_{1,6}=d_{1,7}$, but that will not affect the calculation). The contribution of those medians is $D_{1,3}\left(D_{1,7}-D_{1,6}\right)$. Continuing this way we see that the medians in the second column contribute $D_{1,2}\left(D_{1,6}-D_{1,5}\right)$ and ones in the first column $D_{1,1}\left(D_{1,5}-D_{1,4}\right)$. A median then moves to the seventh column, but by that point its value has dropped, $D_{i, 7}=D_{1,7}-10$. The contribution of those medians is then $\left(D_{1,7}-10\right)\left(D_{1,4}-D_{1,3}\right)$. Similarly for those in sixth and fifth columns we get $\left(D_{1,6}-10\right)\left(D_{1,3}-D_{1,2}\right)$ and $\left(D_{1,5}-10\right)\left(D_{1,2}-D_{1,1}\right)$. Finally the median moves to the fourth column again, staying there remaining $D_{1,1}$ times, contributing $\left(D_{1,4}-10\right) D_{1,1}$. Overall, the sum of all medians is thus
$$
\begin{array}{r}
D_{1,4}\left(10-D_{1,7}\right)+D_{1,3}\left(D_{1,7}-D_{1,6}\right)+D_{1,2}\left(D_{1,6}-D_{1,5}\right)+ \\
D_{1,1}\left(D_{1,5}-D_{1,4}\right)+\left(D_{1,7}-10\right)\left(D_{1,4}-D_{1,3}\right)+\left(D_{1,6}-10\right)\left(D_{1,3}-D_{1,2}\right) \\
+\left(D_{1,5}-10\right)\left(D_{1,2}-D_{1,1}\right)+\left(D_{1,4}-10\right) D_{1,1} .
\end{array}
$$

It is fairly easy to see that this expression is in fact equal to 0 (for example, by considering the linear and quadratic terms separately). This means that the sum of new medians $M_{i}$ is zero, and the sum of the original $m_{i}$ 's is 45 , as wanted,

Solution 2: We will prove a stronger claim: for all $a$, the number of $m_{i}$ 's equal to $a$ equals the number of $m_{i}$ 's equal to $9-a$. (By a pairing argument, this implies that the average of the $m_{i}^{\prime}$ 's is $9 / 2$.) Indeed, for $1 \leq j \leq 10$ let $M_{i, j}$ denote the $j$ th smallest entry in row $i$ of the table (so that $m_{i}=M_{i, 4}$ ); we will show that for all $a$ and $j$, the number of $M_{i, j}$ 's equal to $a$ equals the number of $M_{i, 8-j}$ 's equal to $9-a$.
Henceforth, all row-indices are to be interpreted modulo 10 , and "between" is meant in the inclusive sense.
It follows from the defining property of the table that for all $i$ between 1 and 10 , all $a$ between 0 and 9 , and all $k$ between 0 and $a$, the number of $k$ 's in row $i$ equals the number of $k+a$ 's in row $i+a$. Replacing $a$ by $9-a$, and summing over all $k$ between 0 and $a$, we find that the number of entries between 0 and $a$ in row $i$ equals the
number of entries between $9-a$ and 9 in row $i+9-a$. Hence for all $j$, the number of entries between 0 and $a$ in row $i$ is greater than or equal to $j$ if and only if the number of entries between $9-a$ and 9 in row $i+9-a$ is greater than or equal to $j$. But this means that the $j$ smallest entries in row $i$ are all between 0 and $a$ if and only if the $j$ largest entries in row $i+9-a$ are all between $9-a$ and 9 . That is, $M_{i, j} \leq a$ if and only if $M_{i+9-a, 8-j} \geq 9-a$. Replacing $a$ by $a-1$, we see also that $M_{i, j} \leq a-1$ if and only if $M_{i+10-a, 8-j} \geq 10-a$. Combining the last two facts, we conclude that $M_{i, j}=a$ if and only if $M_{i+10-a, 8-j}=9-a$. Summing over $i$ (and noting that $i+10-a$ varies over $0,1, \ldots, 9 \bmod 10$ as $i$ does), we see that the number of $i$ 's with $M_{i, j}=a$ equals the number of $i$ 's with $M_{i, 8-j}=9-a$, as was claimed above.