Задача 66539

Тема:    [ Теория алгоритмов (прочее) ]

Сложность: 5 Классы: 8,9,10,11

Условие

Автор: Дидин М.

Есть 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⩾(1+2+\cdots +200)\cdot 99+201+202+\dots +400.$$ В свою очередь, $$\begin{array}{rl}P& =S-2B⩽(1+2+\dots +400)\cdot 100-2\cdot (1+2+\cdots +200)\cdot 99-2\cdot (201+202+\dots +400)=\\ & =(201+202+\dots +400)\cdot 98-(1+2+\cdots +200)\cdot 98=\\ & =200\cdot 200\cdot 98=3920000.\end{array}$$

Второй способ.

Для каждого $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+\dots +199+200+199+\dots +2+1)=98\cdot 200\cdot 200.$$

Пример.

Разобьем ходы Пети на $100$ серий по $200$ ходов, в первой серии будем брать камни из первой и второй кучки, во второй — из второй и третьей, и так далее. Последней серией ходов заберем оставшиеся камни из сотой и первой кучки. Тогда ходы из первой и последней серий очков не приносят, а любой другой ход приносит $200$ очков. Всего таких ходов $98\cdot 200$, значит, Петя наберет $98 \cdot 200 \cdot 200 = 3\,920\,000$ очков.

Ответ

3 920 000.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Год	2019
Номер	82
класс
Класс	9
задача
Номер	6