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

Question

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

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

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

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

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

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

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

Взять 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].

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

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

Answer 1

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

В случае, когда x имеет 3 компонента, представьте x как вектор 3x1: x = [x_0 x_1 x_2]' (где ' - операция транспонирования).Каждая итерация цикла выберет переворачивать одно из x_0,x_1,x_2, и операция, которую он выполняет с x, идентична умножению на одну из следующих матриц:

      -1  0  0               1  1  0                1  0  1
s_0 =  1  1  0       s_1 =   0 -1  0        s_2 =   0  1  1
       1  0  1               0  1  1                0  0 -1

, где умножение на s_0- операция, выполняемая, если индекс i=0, s_1 соответствует i=1, а s_2 соответствует i=2.С помощью этого представления вы можете интерпретировать алгоритм как умножение соответствующей матрицы s_i на x на каждой итерации.Таким образом, в первом примере, когда x_1 переворачивается в начале, алгоритм вычисляет: s_1*s_2*s_0*s_1*s_2*s_1[4 -1 -2]' = [0 1 0]'

Тот факт, что выбранный вами индекс не влияет на конечный выходной вектор, возникает из двух интересных свойствs матрицы.Сначала s_i*s_(i-1)*s_i = s_(i-1)*s_i*s(i-1), где i-1 вычисляется по модулю n, количество матриц.Это свойство является единственным, которое необходимо для того, чтобы понять, почему вы получаете тот же результат в примерах с 3 элементами:

s_1*s_2*s_0*s_1*s_2*s_1 = s_1*s_2*s_0*(s_1*s_2*s_1) = s_1*s_2*s_0*(s_2*s_1*s_2), что соответствует выбору x_2 в начале и, наконец,

s_1*s_2*s_0*s_2*s_1*s_2 = s_1*(s_2*s_0*s_2)*s_1*s_2 = s_1*(s_0*s_2*s_0)*s1*s2, что соответствует выбору перевернуть x_2 в начале, но затем выбрать перевернуть x_0 в третьей итерации.

Второе свойство применяется только тогда, когда x имеет 4 илибольше элементов.Это s_i*s_k = s_k*s_i всякий раз, когда k <= i-2, где i-2 снова вычисляется по модулю n.Это свойство проявляется, когда вы рассматриваете форму матриц, когда x имеет 4 элемента:

       -1  0  0  0          1  1  0  0          1  0  0  0          1  0  0  1
s_0 =   1  1  0  0   s_1 =  0 -1  0  0   s_2 =  0  1  1  0   s_3 =  0  1  0  0
        0  0  1  0          0  1  1  0          0  0 -1  0          0  0  1  1
        1  0  0  1          0  0  0  1          0  0  1  1          0  0  0 -1

Второе свойство, по сути, говорит о том, что вы можете поменять порядок, в котором происходят бесконфликтные сальто.Например, в 4-элементном векторе, если вы сначала перевернули x_1, а затем перевернули x_3, это будет иметь тот же эффект, что и сначала переворот x_3, а затем переворачивание x_1.

Answer 2

Я рисую выталкивание отрицательных значений в двух направлениях, пока они не ослабнут.Поскольку сложение является коммутативным, не имеет значения, в каком порядке вы обрабатываете элементы.

Answer 3

Вот наблюдение, когда N делится на 3 ... Вероятно, бесполезно, но я чувствую, что записываю его.

Пусть w (комплексный) - примитивный кубический корень из 1;то есть w^3 = 1 и 1 + w + w^2 = 0.Например, w = cos(2pi/3) + i*sin(2pi/3).

Рассмотрим сумму x_0 + x_1*w + x_2*w^2 + x_3 + x_4*w + x_5*w^2 + ....То есть умножьте каждый элемент последовательности на последовательные степени w и сложите их все.

Что-то в меру интересное происходит с этой суммой на каждом шаге.

Рассмотрим три последовательных числа [a, -b, c] из последовательности, с б положительным.Предположим, что эти элементы совпадают со степенями w, так что эти три числа вносят a - b*w + c*w^2 в сумму.

Теперь выполните шаг на среднем элементе.

После шага,эти числа вносят (a-b) + b*w + (c-b)*w^2 в сумму.

Но так как 1 + w + w^2 = 0, b + b*w + b*w^2 = 0 тоже.Таким образом, мы можем добавить это к предыдущему выражению, чтобы получить a + 2*b*w + c.Что очень похоже на то, что мы имели до шага.

Другими словами, шаг просто прибавил 3*b*w к сумме.

Если бы три последовательных числа были выровнены со степенямиw чтобы внести (скажем) a*w - b*w^2 + c, получается, что шаг добавит 3*b*w^2.

Другими словами, независимо от того, как силы w совпадают с тремя числами,шаг увеличивает сумму на 3*b, 3*b*w или 3*b*w^2.

К сожалению, поскольку w^2 = -(w+1), это на самом деле не дает стабильно увеличивающейся функции.Так что, как я уже сказал, вероятно, бесполезно.Но все же кажется, что разумной стратегией является поиск «подписи» для каждой позиции, которая монотонно меняется с каждым шагом ...