将整数数组转换为非负整数数组

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,无论在任何步骤中选择哪个索引,通过这些步骤的次数与结果向量相同.至少对于我来说,这个过程在有限的时间内终止是不明显的,更不用说具有这种不错的不变性.

例:

采取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].

我有一个争论,为什么这是真的,但在我看来过于复杂(它与Coxeter小组有关).有没有人有更直接的方式来思考为什么会这样？即使找到这个终止的原因也会很棒.

奖励指向任何找到确定给定数组步骤数的方法(不经过整个过程).

Answer 1

我认为，无论您在每一步选择什么索引，要了解为什么输出向量和步骤数都相同的最简单方法是将问题视为一堆矩阵和向量乘法。

对于具有 3 个分量的情况x，可将其视为x3x1 向量：（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 个或更多元素的情况。每当where再次计算模s_i*s_k = s_k*s_i时。当您考虑具有 4 个元素的矩阵形式时，此属性就很明显：k <= i-2i-2nx

       -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_3x_1