|
|
 |
Условие
Есть 100 кучек по 400 камней в каждой. За ход Петя
выбирает две кучки, удаляет из них по одному камню и получает за это столько очков, каков теперь модуль разности
числа камней в этих двух кучках. Петя должен удалить все
камни. Какое наибольшее суммарное количество очков он
может при этом получить?
Решение
Оценка.
Пронумеруем в каждой куче камни по порядку. Без потери общности можно считать, что Петя, выбрав кучку, всегда берет из нее камень с наибольшим номером. Ясно, что каждый ход приносит столько очков, чему равна разность между большим и меньшим из чисел на камнях, взятых на этом ходу.
Первый способ.
Пусть Петя набрал $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$ очков.
