Цена игры

Сначала докажем, что Саша может всегда получать результат из отрезка . Будем считать, что текущее число на доске неположительно (в противном случае можно заменить все знаки в рассуждениях на противоположные). Разберем два случая для числа , называемым Димой на очередном раунде.

Случай 1. Пусть .

Тогда поставим знаки так: , а остальные знаки расставим произвольным образом. Так как , результат будет положительным, и число на доске не станет меньше -256. С другой стороны, результат не превосходит , значит, число на доске не станет больше 256.

Случай 2. Пусть .

Если текущее число на доске не равно -256 , Саша может поставить знак минус перед числом 512 и плюсы перед остальными знаками. Результат после вычислений будет равен -1 , поэтому число на доске останется на отрезке . Если же текущее число на доске равно - 256, Саша может поставить знак минус перед числом 256 и плюсы перед остальными знаками. Результат вычислений будет равен 511, поэтому следующее число на доске будет равно 255 за пределы отрезка Саша не вышел.

Теперь докажем, что Дима может добиться результата 256. Будем называть всегда . Если Саша ставит плюс перед числом 512 , результат вычислений будет равен +1 , и число на доске увеличится. Чтобы не допустить появления числа, превосходящего 255, Саше нужно в какой-то момент поставить знак плюс перед другим числом. В такой ситуации результат вычисления отрицательный и по модулю не меньше . Поэтому следующее число на доске не больше, чем , и Дима добился желаемого результата.