Разделы 
Дополнительно
Задача по математике - 3607
2019-06-12 
Написано 20 чисел: $1, 2, \cdots, 20$. Двое играющих по очереди ставят перед этими числами знаки « + » или «-» (знак можно ставить перед любым свободным числом). Первый стремится к тому, чтобы полученная после расстановки всех 20 знаков сумма была как можно меньше по модулю. Какую наибольшую по модулю сумму может обеспечить себе второй?
Решение:
Опишем стратегию второго игрока, которая обеспечит ему такую сумму. Разобьем все числа на пары $(1,2), (3,4), \cdots (19, 20)$. Каждый раз, когда первый ставит какой-нибудь знак перед одним из чисел, кроме 19 и 20, второй должен ставить противоположный знак перед числом той же пары. Как только первый ставит какой-нибудь знак перед числом последней пары, второй ставит тот же знак перед другим из этих чисел. Ясно, что окончательная сумма по модулю будет не меньше чем
$19 + 20 - \underbrace{1 - 1 - 1 - \cdots - 1}_{9 \: раз} = 30$.
Докажем теперь, что первый может не позволить второму выбрать больше 30, если будет при каждом своем ходе ставить перед наибольшим из оставшихся чисел знак, противоположный знаку имеющейся к этому моменту суммы (если сумма равна нулю, то ставится плюс).
Рассмотрим некоторую партию. Пусть $k$-й ход - последний, в результате которого сумма меняет знак (включая ходы, перед которыми сумма равна нулю). За первые $k - 1$ ходов будут заведомо использованы числа $20, 19, 18, \cdots, 20 - (k - 1)$. Так что максимальная по модулю сумма, которая может получиться после $k$-го хода $20 - (k - 1) + 20 - k = 41 - 2k$. За каждый из следующих $10 - к$ ходов сумма уменьшается по крайней мере на 1, так как первый каждый раз вычитает из модуля суммы наибольшее из оставшихся чисел $m$, а второй не может добавить к нему больше $m - 1$. Итак, в результате сумма будет не больше чем $41 - 2k - (10 - k) = 31 - k \leq 30$.
Ответ: 30.
Написано 20 чисел: $1, 2, \cdots, 20$. Двое играющих по очереди ставят перед этими числами знаки « + » или «-» (знак можно ставить перед любым свободным числом). Первый стремится к тому, чтобы полученная после расстановки всех 20 знаков сумма была как можно меньше по модулю. Какую наибольшую по модулю сумму может обеспечить себе второй?
Решение:
Опишем стратегию второго игрока, которая обеспечит ему такую сумму. Разобьем все числа на пары $(1,2), (3,4), \cdots (19, 20)$. Каждый раз, когда первый ставит какой-нибудь знак перед одним из чисел, кроме 19 и 20, второй должен ставить противоположный знак перед числом той же пары. Как только первый ставит какой-нибудь знак перед числом последней пары, второй ставит тот же знак перед другим из этих чисел. Ясно, что окончательная сумма по модулю будет не меньше чем
$19 + 20 - \underbrace{1 - 1 - 1 - \cdots - 1}_{9 \: раз} = 30$.
Докажем теперь, что первый может не позволить второму выбрать больше 30, если будет при каждом своем ходе ставить перед наибольшим из оставшихся чисел знак, противоположный знаку имеющейся к этому моменту суммы (если сумма равна нулю, то ставится плюс).
Рассмотрим некоторую партию. Пусть $k$-й ход - последний, в результате которого сумма меняет знак (включая ходы, перед которыми сумма равна нулю). За первые $k - 1$ ходов будут заведомо использованы числа $20, 19, 18, \cdots, 20 - (k - 1)$. Так что максимальная по модулю сумма, которая может получиться после $k$-го хода $20 - (k - 1) + 20 - k = 41 - 2k$. За каждый из следующих $10 - к$ ходов сумма уменьшается по крайней мере на 1, так как первый каждый раз вычитает из модуля суммы наибольшее из оставшихся чисел $m$, а второй не может добавить к нему больше $m - 1$. Итак, в результате сумма будет не больше чем $41 - 2k - (10 - k) = 31 - k \leq 30$.
Ответ: 30.
