Question

Даю 20 баллов! Имеется 2003 целых числа с суммой 0. Разрешается выбрать любые 300 чисел и поменять у каждого из них знак либо уменьшить каждое на 1. Докажите, что при помощи таких операций можно получить 2003 нуля.

Answer 1

Пусть еще не все числа нули.

• Выбираем одно положительное число, одно отрицательное и 299 любых других чисел (если все числа были бы одного знака и хотя бы одно отличалось от нуля, то сумма не могла бы быть равна нулю, так что такой выбор всегда возможен).
• Берем положительное число и выбранные 299 чисел. Вычитаем из них 1.
• Берем отрицательное число и выбранные 299 чисел. Меняем им знак, вычитаем из них 1, опять меняем знак.

В результате изменятся только выбранное отрицательное и выбранное положительное числа: к отрицательному будет прибавлено 1, из положительного - вычтено 1. Каждое из 299 чисел не меняется:

$x\mapsto x-1\mapsto 1-x\mapsto -x\mapsto x$

Сумма не поменяется, так что такие действия можно продолжать до тех пор, пока все числа не станут нулями.

Процесс завершится за конечное число шагов: действительно, на каждом шаге сумма модулей всех чисел - неотрицательное целое число - уменьшается на 2, поэтому, если сумма модулей исходных чисел равна 2S, за S итераций сумма модулей станет равна 0, что возможно, только если все числа - нули.

Answer 2

Для доказательства этого утверждения воспользуемся принципом Дирихле, который гласит, что если имеется n+1 объектов, которые необходимо распределить по n ящикам, то обязательно найдется хотя бы один ящик, в котором будет более одного объекта.

Рассмотрим 2003 числа, сумма которых равна 0. Если у нас найдутся хотя бы два числа с одним и тем же значением, то мы можем выбрать оба этих числа и уменьшить их на 1, таким образом, сумма останется неизменной, но количество нулей увеличится на 2.

Теперь предположим, что все 2003 числа различны. Рассмотрим сумму всех возможных комбинаций из 300 чисел (выбранных из данных 2003 чисел). Количество таких комбинаций можно рассчитать по формуле биномиального коэффициента C(2003, 300). Это число будет больше количества различных значений сумм, которые можно получить из 300 чисел. По принципу Дирихле обязательно найдется хотя бы одна сумма, которую можно получить несколькими различными комбинациями чисел.

Допустим, найдется сумма S, которую можно получить двумя различными комбинациями чисел. Пусть эти комбинации состоят из чисел a_1, a_2, ..., a_300 и b_1, b_2, ..., b_300 соответственно.

Тогда мы можем рассмотреть разность S = (a_1 + a_2 + ... + a_300) - (b_1 + b_2 + ... + b_300). Обратим внимание, что все числа в этой разности будут различными, так как мы предположили, что все исходные 2003 числа различны. Каждое из чисел в разности может быть либо положительным, либо отрицательным (так как S может быть получено двумя различными комбинациями, которые отличаются только знаками чисел).

Итак, у нас есть сумма 300 различных чисел (возможно, со знаками) с абсолютной величиной S. Теперь мы можем изменить знак у всех чисел в одной из комбинаций (например, у b_1, b_2, ..., b_300) и уменьшить все числа в другой комбинации (a_1, a_2, ..., a_300) на 1. Это приведет к получению двух комбинаций с суммой 0 (так как сумма S будет скомпенсирована).

Таким образом, в любом случае у нас найдется пара одинаковых чисел или две различные комбинации с одинаковой суммой, что позволяет получить 2003 нуля с помощью описанных операций.