Let $p_{1}, p_{2}, \ldots, p_{30}$ be a permutation of the numbers $1,2, \ldots, 30$. For how many permutations does the equality $\sum_{k=1}^{30}\left|p_{k}-k\right|=450$ hold?

Answer: $(15 !)^{2}$.
Let us define pairs $\left(a_{i}, b_{i}\right)$ such that $\left\{a_{i}, b_{i}\right\}=\left\{p_{i}, i\right\}$ and $a_{i} \geqslant b_{i}$. Then for every $i=1, \ldots, 30$ we have $\left|p_{i}-i\right|=a_{i}-b_{i}$ and

$$
\sum_{i=1}^{30}\left|p_{i}-i\right|=\sum_{i=1}^{30}\left(a_{i}-b_{i}\right)=\sum_{i=1}^{30} a_{i}-\sum_{i=1}^{30} b_{i}
$$

It is clear that the sum $\sum_{i=1}^{30} a_{i}-\sum_{i=1}^{30} b_{i}$ is maximal when

$$
\left\{a_{1}, a_{2}, \ldots, a_{30}\right\}=\{16,17, \ldots, 30\} \quad \text { and } \quad\left\{b_{1}, b_{2}, \ldots, b_{30}\right\}=\{1,2, \ldots, 15\}
$$

where exactly two $a_{i}$ 's and two $b_{j}$ 's are equal, and the maximal value equals

$$
2(16+\cdots+30-1-\cdots-15)=450 .
$$

The number of such permutations is $(15 !)^{2}$.

#