Задача 109550
|
|
 |
Условие
На доске написано число 0. Два игрока по очереди приписывают справа к выражению на доске: первый – знак + или - , второй – одно из натуральных чисел от 1 до 1993. Игроки делают по 1993 хода, причем второй записывает каждое из чисел от 1 до 1993 ровно по одному разу. В конце игры второй игрок получает выигрыш, равный модулю алгебраической суммы, написанной на доске. Какой наибольший выигрыш он может себе гарантировать?Решение
1993. Пусть первый игрок действует следующим образом: своим первым ходом он ставит знак, противоположный знаку числа, являющегося значением выражения на доске, если это число не равно нулю, и любой знак в противном случае. Тогда после каждого (в том числе и последнего) хода игрока модуль алгебраической суммы, написанной на доске, будет не больше 1993. Значит, второй игрок не может гарантировать себе выигрыш, больший 1993. Покажем, что он может добиться выигрыша, равного 1993. Составим две последовательности по 996 чисел с равными суммами:и
Второй игрок может считать отдельно количество плюсов и минусов, поставленных первым. Стратегия второго игрока заключается в том, чтобы писать на доске очередное число из первой последовательности после каждого плюса с номером не более 996 и из второй последовательности после каждого минуса с номером не более 996. Как только один из знаков появится на доске в 997-й раз, второму следует написать после него число 1993. Тогда сумма всех чисел на доске, перед которыми стоит этот знак, по модулю превысит сумму всех остальных чисел от 1 до 1992 по крайней мере на 1993. Поэтому далее второй игрок может выписывать еще не использованные числа от 1 до 1992 в любом порядке. Итак, второй игрок может гарантировать себе выигрыш, равный 1993.
