|
|
 |
Условие
Есть 100 кучек по 400 камней в каждой. За ход Петя выбирает две кучки, удаляет из них по одному камню и получает за это столько очков, каков теперь модуль разности числа камней в этих двух кучках. Петя должен удалить все камни. Какое наибольшее суммарное количество очков он может при этом получить?
Решение
Оценка. Будем считать, что камни в кучках лежат один на другом, причём из выбранных кучек Петя берет верхние (на данный момент) камни.
Пронумеруем камни в каждой кучке снизу вверх числами от 1 до 400. Тогда число очков, которое Петя получает на каждом ходу, равно разности номеров удаляемых камней. В результате он получит сумму вида $|a_{1} – a_{2}| + |a_{3} – a_{4}| + ... + |a_{39999} – a_{40000}|$, где $a_i$ – номера соответствующих камней.
Заметим, что после раскрытия скобок получается алгебраическая сумма $S$ ста чисел 400, ста чисел 399, ..., ста двоек и ста единиц, причём ровно перед половиной этих чисел стоит знак минус.
Назовём числа от 1 до 200 маленькими, а остальные – большими. Если бы разрешалось брать из кучек произвольные камни, то максимальное значение $S$, очевидно, достигается, когда все большие числа входят в $S$ со знаком плюс, а все маленькие – со знаком минус.
Такая сумма равна
100(400 + 399 + ... + 201 – 200 – 199 – ... – 1) =
100 ((400 – 200) + (399 – 199) + ... + (201 – 1)) = 100·200².
Заметим, однако, что каждое большое число хотя бы один раз войдёт в сумму со знаком минус: это произойдёт, например, в тот момент, когда Петя в первый раз удалит камень с этим номером. Аналогично каждое из 200 маленьких чисел хотя бы один раз войдёт в сумму в сумму со знаком плюс (в тот момент, когда Петя удалит последний камень с этим номером).
Поэтому максимальный результат Пети не превышает 99(400 + 399 + ... + 201) $ndash; 99(200 + 199 + ... + 1) – (400 + 399 + ... + 201) + (200 + 199 + ... + 1) = 98·200².
Пример. Добиться указанного результата можно, например, так. За первые 200 ходов Петя забирает по 200 камней из первых двух кучек (при этом 200 больших чисел – каждое по разу – получают знак минус). За следующие 200 ходов он снимает 200 верхних камней из третьей кучки и 200 нижних из первой кучки, далее по 200 камней из второй и четвёртой, третьей и шестой, ..., 98-й и 100-й кучек (при этом все числа входят с "правильными" знаками). Наконец остаётся по 200 нижних камней в последних двух кучках, которые и снимаются за последние 200 ходов (и возникает 200 знаков плюс перед числами с 200 по 1).
Ответ
3920000.
Замечания
12 баллов
