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

Начните с массива целых чисел, чтобы сумма значений составляла некоторое натуральное число 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, независимо от того, какой индекс выбран на любом шаге, количество шагов, пройденных этими шагами, такое же, как и результирующий вектор. Даже не очевидно (по крайней мере, для меня), что этот процесс заканчивается за конечное время, не говоря уже о том, что это хорошее свойство инвариантности.

Пример:

Возьмем 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]

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

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

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

Ответ 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, число матриц. Это свойство - единственное, что необходимо для того, чтобы понять, почему вы получаете тот же результат в примерах с тремя элементами:

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, что соответствует выбору flip 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

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

Ответ 2

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

Ответ 3

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

Пусть w (complex) - примитивный кубический корень из 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] из последовательности, причем b положительно. Предположим, что эти элементы совпадают с степенями 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), это фактически не приводит к неуклонно возрастающей функции. Итак, как я уже сказал, вероятно, не полезно. Но по-прежнему кажется разумной стратегией - искать "подпись" для каждой позиции, которая монотонно изменяется с каждым шагом...