Diding M.

There are 100 piles, each with 400 stones. In one move, Petya selects two piles, removes one stone from each, and earns as many points as the absolute difference in the number of stones in these two piles. Petya must remove all the stones. What is the maximum total number of points he can earn in this process?

#
## Evaluation.

Let's number the stones in each pile in order. Without loss of generality, we can assume that Petya, when choosing a pile, always takes the stone with the largest number from it. It is clear that each move brings as many points as the difference between the larger and smaller numbers on the stones taken on that move.

## First Method.

Suppose Petya scored $P = a_1 - b_1 + a_2 - b_2 + \cdots + a_n - b_n$ points, where $a_i$ and $b_i$ are the larger and smaller numbers on the stones chosen by Petya on the move with number $i$, and $n=20000$ is the total number of moves. Note that among the numbers $a_1, b_1, \ldots, a_n, b_n$, each number from $1$ to $400$ appears exactly $100$ times, since in each of the hundred piles, the stones are numbered with all different numbers from $1$ to $400$. Let $S = a_1 + b_1 + a_2 + b_2 + \cdots + a_n + b_n = (1 + 2 + \cdots + 400) \cdot 100$, and $B = b_1 + b_2 + \cdots + b_n$. Then $P = S - 2B$, and the problem reduces to estimating the smallest possible value of the number $B$.

Note that each number from $1$ to $400$ will appear at least once among the numbers $a_1, \ldots, a_n$, since each number will at least once be the largest among the numbers written on the stones. Similarly, each number from $1$ to $400$ will appear at least once among the numbers $b_1, \ldots, b_n$, since each number will at least once be the smallest among the numbers written on the stones. Therefore, in the set $b_1, \ldots, b_n$, there can be no fewer than one and no more than $99$ of each of the numbers from $1$ to $400$, hence $B \geq (1+2+\cdots+200) \cdot 99 + 201+202+\cdots+400$. In turn,
\[
\begin{align*}
P &= S - 2B \leq (1 + 2 + \cdots + 400) \cdot 100 - 2 \cdot (1+2+\cdots+200) \cdot 99 - 2 \cdot (201+202+\cdots+400) \\
&= (201+202+\cdots+400) \cdot 98 - (1+2+\cdots+200) \cdot 98 \\
&= 200 \cdot 200 \cdot 98 = 3,920,000.
\end{align*}
\]

Second Method.

For each $n \in \{1, \ldots, 399\}$, let's calculate $d_n$ - the number of moves such that exactly one of the two stones Petya takes has a number greater than $n$. Then the sum of all such $d_n$ is exactly the sum of points at the end of the game. Indeed, a move in which Petya takes stones with numbers $a$ and $b$ ($a \geq b$) will increase the numbers $d_b, d_{b+1}, \ldots, d_{a-1}$ by one.

For $n \leq 200$, the inequality $d_n \leq 98n$ holds, since there are a total of $100n$ stones with numbers less than or equal to $n$, but in the last $n$ moves, we take two such stones each time, because there are no others left. For $n > 200$, the estimate $d_n \leq 98 \cdot (400-n)$ holds, since there are a total of $100 \cdot (400-n)$ stones with numbers greater than $n$, but in the first $n$ moves, we take two such stones each time, because others are not yet available. Summing these estimates, we get $98(1+2+\cdots+199+200+199+\cdots+2+1) = 98 \cdot 200 \cdot 200 / 2$.

## Example.

Let's divide Petya's moves into $100$ series of $200$ moves each, in the first series we will take stones from the first and second piles, in the second series - from the second and third piles, and so on. The last series of moves will take the remaining stones from the hundredth and first piles. Then the moves from the first and last series do not bring points, and any other move brings $200$ points. There are a total of $98 \cdot 200$ such moves, so Petya will score $98 \cdot 200 \cdot 200 = 3,920,000$ points.