Максимизация очков в задаче Пети: 100 кучек камней

  Оценка. Будем считать, что камни в кучках лежат один на другом, причём из выбранных кучек Петя берет верхние (на данный момент) камни. Пронумеруем камни в каждой кучке снизу вверх числами от 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).