NMO Selection Tests for the Junior Balkan Mathematical Olympiad - Fourth Selection Test

Consider a certain snake. For each line $i \in \{1, 2, \dots, n\}$ of the table, we denote by $a_i$ and $b_i$ the numbers of the columns corresponding to the first and last cell, respectively, that the snake has on line $i$. We observe that $a_{i+1} = b_i$ for any $i \in \{1, 2, \dots, n-1\}$, therefore the snake is determined by the values $a_1, b_1, b_2, \dots, b_n \in \{1, 2, \dots, m\}$. We deduce that the total number of snakes is $m^{n+1}$.

Let $(k, p)$ be some cell of the table. The snakes that contain this cell are those for which $a_k \le p \le b_k$. For these, we can choose $a_k$ and $b_k$ in $2p(m-p+1)-1$ ways, and the numbers $a_1, b_1, b_2, \dots, b_n$, other than $a_k$ and $b_k$, in $m^{n-1}$ ways. Thus, the cell $(k, p)$ is counted by $m^{n-1}(2pm-2p^2+2p-1)$ times in all the snakes in the table.

It follows that the cells on column $p$ contribute with $n \cdot m^{n-1}(2pm - 2p^2 + 2p - 1)$ to the total $T$ of the lengths of all snakes in the table, therefore
$$T = \sum_{p=1}^{m} n \cdot m^{n-1} (2pm - 2p^2 + 2p - 1) = n \cdot m^{n+1} (m+1) - \frac{n \cdot m^n (m+1)(2m+1)}{3} + n \cdot m^{n+1} = \frac{n \cdot m^n (m^2 + 3m - 1)}{3}.$$
The arithmetic mean of the lengths of all the snakes in the table is $\frac{n(m^2+3m-1)}{3m}$.