Превращение массива целых чисел в массив неотрицательных целых чисел

Начать с массива целых чисел, чтобы сумма значений была некоторым положительным целым числом S . Следующая процедура всегда завершается одним и тем же числом шагов с одинаковыми результатами. Почему это?

Начните с массива x = [x_0, x_1, ..., x_N-1] таким образом, чтобы все x_i были целыми числами. Пока есть отрицательная запись, сделайте следующее:

• Выберите любой индекс i так, чтобы x_i .

• Добавьте x_i (отрицательное число) к x_ (i-1% N) .

• Добавьте x_i (a отрицательное число) на x_ (i + 1% N) .

• Замените x_i на -x_i (положительное число).

Этот процесс поддерживает свойство x_0 + x_1 + ... + x_N-1 = S . Для любого заданного начального массива x , независимо от того, какой индекс выбран на любом шаге, количество раз, которое нужно пройти через эти шаги, совпадает с результирующим вектором. Даже не очевидно (по крайней мере для меня), что этот процесс завершается за конечное время, не говоря уже о том, что он обладает этим прекрасным свойством инвариантности.

ПРИМЕР:

Возьмем x = [4, -1, -2 ] и перевернув x_1 , чтобы начать, результат будет

[4, -1, -2]
[3, 1, -3]
[0, -2, 3]
[-2, 2, 1]
[2, 0, -1]
[1, -1, 1]
[0, 1, 0]

С другой стороны, переворот x_2 для начала дает

[4, -1, -2]
[2, -3, 2]
[-1, 3, -1]
[1, 2, -2]
[-1, 0, 2]
[1, -1, 1]
[0, 1, 0]

, и последний способ дать это решение с массивами, перевернутыми с третьего и ниже, если вы выберете x_2 вместо x_0 для переворота в третьем массиве. Во всех случаях 6 шагов приводят к [0,1,0] .

У меня есть аргумент в пользу того, почему это правда, но мне кажется, что это слишком сложно (это связано с Группы Кокстера ). У кого-нибудь есть более прямой способ подумать, почему это происходит? Было бы здорово даже найти причину, по которой это должно прекратиться.

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