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?
Evaluation. Let's assume that the stones in the piles are stacked on top of each other, and Petya takes the top (at the moment) stones from the selected piles. Let's number the stones in each pile from bottom to top with numbers from 1 to 400. Then the number of points Petya gets on each move is the difference in the numbers of the removed stones. As a result, he will get a sum of the form \( |a_1 - a_2| + |a_3 - a_4| + \ldots + |a_{39999} - a_{40000}| \) for the corresponding stones.

Notice that after expanding the brackets, we get an algebraic sum \( S \) of one hundred numbers 400, one hundred numbers 399, ..., one hundred twos, and one hundred ones, with a minus sign in front of exactly half of these numbers.

Let's call the numbers from 1 to 200 small, and the rest large. If it were allowed to take any stones from the piles, then the maximum value of \( S \) would obviously be achieved when all large numbers enter \( S \) with a plus sign, and all small numbers with a minus sign. Such a sum is equal to \( 100(400 + 399 + \ldots + 201 - 200 - 199 - \ldots - 1) = 100((400 - 200) + (399 - 199) + \ldots + (201 - 1)) = 100 \cdot 200^2 \). However, note that each large number will enter the sum with a minus sign at least once: this will happen, for example, when Petya first removes a stone with this number. Similarly, each of the 200 small numbers will enter the sum with a plus sign at least once (when Petya removes the last stone with this number). Therefore, the maximum result for Petya does not exceed \( 99(400 + 399 + \ldots + 201) - 99(200 + 199 + \ldots + 1) - (400 + 399 + \ldots + 201) + (200 + 199 + \ldots + 1) = 98 \cdot 200^2 \).

Example. The specified result can be achieved, for example, as follows. In the first 200 moves, Petya takes 200 stones from the first two piles (in this case, 200 large numbers each get a minus sign once). In the next 200 moves, he removes 200 top stones from the third pile and 200 bottom stones from the first pile, then 200 stones from the second and fourth piles, the third and sixth piles, ..., the 98th and 100th piles (in this case, all numbers enter with the "correct" signs). Finally, there are 200 bottom stones left in the last two piles, which are removed in the last 200 moves (and 200 plus signs appear before the numbers from 200 to 1).

## Answer

3920000.

| $\left[\begin{array}{c}\text { Weighings } \\ {\left[\begin{array}{c}\text { Processes and operations }\end{array}\right]} \\ {[\text { Theory of algorithms (other).] }} \\ \text { Evaluation + example }\end{array}\right]$ |  |  |  |
| :---: | :---: | :---: | :---: |
|  |  |  |  |
|  |  |  |  |

There is a chain segment consisting of 60 links, each weighing 1 g. What is the minimum number of links that need to be broken so that the resulting parts can be used to form all weights from 1 g, 2 g, 3 g, ..., 60 g (a broken link also weighs 1 g)?

## Solution

Answer: 3 links. Let's determine the maximum \( n \) for which it is sufficient to break \( k \) links of an \( n \)-link chain so that the resulting parts can form all weights from 1 to \( n \). If \( k \) links are broken, then any number of links from 1 to \( k \) can be formed from them. But \( k+1 \) links we cannot form if there is no part with \( k+1 \) or fewer links (we do not consider the broken links here). The most advantageous is to have a part with exactly \( k+1 \) links. Then we can get any number of links from 1 to \( 2k+1 \). (Otherwise, we can only get the number of links from 1 to \( l_1 + k \), where \( l_1 \leq k \)). Then the most advantageous is to have a part with \( 2(k+1) \) links, then with \( 4(k+1) \) links, and so on. Thus, if we break \( k \) links, the most advantageous situation is when the \( k+1 \) parts obtained consist of \( k+1, 2(k+1), 4(k+1), 8(k+1), \ldots, 2^k(k+1) \) links (we do not consider the broken links here). In this case, we can form any number of links from 1 to \( n = 2^{k+1}(k+1) - 1 \). Thus, if \( 2^k k \leq n \leq 2^{k+1}(k+1) - 1 \), then \( k \) breaks are sufficient and \( k-1 \) breaks are insufficient. In particular, if \( 24 \leq n \leq 63 \), then the minimum number of broken links is 3. The four parts obtained by breaking should consist of \( 4, 8, 16, 29 \) links.