задачка (математическое)

[avva]

В рабочую рассылку прислали хорошую задачку.

У вас есть пять целых чисел N1, N2, N3, N4, N5. Вы повторяете следующую операцию: выбираете какое-нибудь отрицательное среди них, меняете его знак с минуса на плюс, и вычитаете его положительное значение из обоих его соседей. Например, если у вас есть [10, 5, -4, -8, 2] и выбрали -4, то получится [10, 1, 4, -12, 2]. У крайних чисел один из соседей берется с второго края (так, соседи N1 - N2 и N5). Обратите внимание, что сумма всех чисел после этой операции не меняется.

Дано, что вначале сумма всех чисел положительна. Доказать или опровергнуть: невзирая на то, как выбираются числа, после конечного числа операций отрицательных чисел не останется.

Комменты не скрываются.

Comments

[waxtep.livejournal.com]

по-моему, можно так: представим "+1" как белый шарик, а "-1" - как черный. Неотрицательные числа представляем в виде соотв. кол-ва белых шариков (в т.ч. 0), а отрицательные - в виде фиксированного числа белых шариков, равного ceil(avg(x)) и соотв. числа черных шариков. Если в некоторой ячейке оказывается больше или равно белых шариков, чем черных, черные шарики "рекомбинируют" с белыми (из игры выбывают равные кол-ва черных и белых шариков). Каждый ход в игре сводится к перекладыванию черных и белых шариков, с обязательной рекомбинацией => кол-во черных шариков монотонно убывает => их в конце концов не останется.

[waxtep.livejournal.com]

не, не работает, 1,-2,-1 => -1,2,-3 - как ни крути, а еще один черный шарик надо родить. хнык.