Максимальные очки Пети в игре с камнями

Оценка. Пронумеруем в каждой куче камни по порядку. Без потери общности можно считать, что Петя, выбрав кучку, всегда берет из нее камень с наибольшим номером. Ясно, что каждый ход приносит столько очков, чему равна разность между большим и меньшим из чисел на камнях, взятых на этом ходу. Первый способ. Пусть Петя набрал $P = a_1 - b_1 + a_2 - b_2 + \ldots + a_n - b_n$ очков, где $a_i$ и $b_i$ соответственно большее и меньшее числа на камнях, выбранных Петей на ходу с номером $i$, а $n = 20000$ — общее число ходов. Заметим, что среди чисел $a_1, b_1, \ldots, a_n, b_n$ каждое число от $1$ до $400$ встречается ровно $100$ раз, так как в каждой кучке из ста кучек на камнях написаны все различные числа от $1$ до $400$. Пусть $S = a_1 + b_1 + a_2 + b_2 + \ldots + a_n + b_n = (1 + 2 + \ldots + 400) \cdot 100$, a$B = b_1 + b_2 + \ldots + b_n$. Тогда$P = S - 2B$, и задача сводится к оценке наименьшего возможного значения числа $B$.

Заметим, что каждое число от $1$ до $400$ хотя бы раз встретится среди чисел $a_1, \ldots, a_n$, так как каждое число хотя бы раз за игру будет наибольшим среди написанных на камнях. Аналогично, каждое число от $1$ до $400$ хотя бы раз встретится и среди чисел $b_1, \ldots, b_n$, так как каждое число хотя бы раз за игру будет наименьшим среди написанных на камнях. С учетом сказанного, в наборе $b_1, \ldots, b_n$ может быть не менее чем по одному и не более чем по $99$ каждого из чисел от $1$ до $400$, следовательно, $$B \geqslant (1+2+\cdots+200) \cdot 99 + 201 + 202 + \ldots + 400.$$ В свою очередь, \begin{align*} P &= S - 2B \leqslant (1 + 2 + \ldots + 400) \cdot 100 - 2 \cdot (1+2+\cdots+200) \cdot 99 -2 \cdot (201 + 202 + \ldots + 400) = \ &=(201+ 202 + \ldots + 400)\cdot 98 - (1+2+\dots+200) \cdot 98 =\ &= 200 \cdot 200 \cdot 98 = 3,920,000. \end{align*} Второй способ. Для каждого $n \in {1, \ldots, 399}$ подcчитаем $d_n$ — число таких ходов, что ровно на одном из двух камней, которые берет Петя, написано число, большее $n$. Тогда сумма по всем таким $d_n$ в точности равна сумме очков в конце игры. В самом деле, ход, в который Петя взял камни с числами $a$ и $b$ ($a \geqslant b$), увеличит на единицу числа $d_b$, $d_{b+1}$, ..., $d_{a-1}$ — всего как раз $a - b$ чисел.

При $n\leqslant 200$ справедливо неравенство $d_n\leqslant 98n$, так как всего камней с номерами, меньшими либо равными $n$, $100n$ штук, но последними $n$ ходами мы берем по два таких камня, потому что других уже не осталось. Для $n>200$ верна оценка $d_n \leqslant 98\cdot (400-n)$, так как всего камней с номерами, большими $n$, $100\cdot (400-n)$ штук, но первыми $n$ ходами мы берем по два таких камня, потому что другие еще не доступны. Суммируя эти оценки, получаем $$98(1+2+\ldots+199+200+199+\ldots+2+1)=98 \cdot 200 \cdot 200.$$ Пример.Разобьем ходы Пети на $100$ серий по $200$ ходов, в первой серии будем брать камни из первой и второй кучки, во второй — из второй и третьей, и так далее. Последней серией ходов заберем оставшиеся камни из сотой и первой кучки. Тогда ходы из первой и последней серий очков не приносят, а любой другой ход приносит $200$ очков. Всего таких ходов $98\cdot 200$, значит, Петя наберет $98 \cdot 200 \cdot 200 = 3,920,000$ очков.