IS Array of Positive Integers Always 'Equalizable' With This Strategy?

Question

A little bit of history first. I have asked this question here some days ago. Quoting from there:

An array $A$ is given that has only positive integers in it. The objective is to equalize the array in minimum possible steps. In every step all but one element are incremented by a fixed step size. The possible step sizes are given in another array $D$.For example, if $A=\{2,2,3,7\}$ and $D=\{1,2,5\}$ we can equalize $A$ in two steps, first adding $A=\{5,5,5,0\}$ to get $A=\{7,7,8,7\}$ and then adding $\{1,1,0,1\}$ to get $A=\{8,8,8,8\}$.

If $A$ has just two elements, this reduces to something like a change-making problem. If $\Delta=min(A[0],A[1])$, if I can make change for $\Delta$ using only the given steps from $D=\{1,2,5\}$, I can equalize the array by holding the larger element constant while incrementing the smaller element by the same values that I used to make change for $\Delta$. However,if it's not possible to make change for delta, it's not clear if the two elements can converge two some larger value following this strategy.

I would like to know if this strategy of withholding one element and incrementing the rest by a chosen 'delta' will always make all elements equal in some finite number of steps.

Answer 1

If the GCD of the array D is larger than 1, then this cannot always be done. The simplest example is $A = \{1,2\},D=\{2\}$. In contrast, if the GCD of the array D is 1, then it is known that large enough integers can be represented as positive linear combinations of elements of D. In particular, there is an integer $N$ such that $N-a$ can be represented for all $a \in A$. Summing all these representations will equalize the array.

For example, when $A = \{2,3,7\}$ and $D = \{1,2,5\}$, we can add $\{1,0,0\}$ once and $\{1,1,0\}$ four times, reflecting the representations $7-2=5 \times 1$, $7-3=4 \times 1$, $7-7 = 0 \times 1$. Even when $D = \{2,5\}$ this has a solution: using $11 = 3 \times 2 + 1 \times 5$, $10 = 2 \times 5$, $6 = 3 \times 2$, we can add $\{2,0,2\}$ three times, $\{5,5,0\}$ once, and $\{0,5,0\}$ once to get $\{13,13,13\}$.

Answer 2

Note that $A +\{x,x,0,x\}$ is equivalent to $A + \{x,x,x,x\}-\{0,0,x,0\}$. Since adding the same value does not affect equalization, so step is isomorphic to subtracting a value in $A$ from a number in $D$.

Furthermore, we could subtract $\min A$ from the array since this does not affect equalization either. Now equalizing the array is equivalent to bring the whole array to zero. Using your example, we have $$A_\text{original} = \{2,2,3,7\} \implies A_\text{reduced} = \{0,0,1,5\} $$ We use two steps A[2] -= 1 and A[3] -= 5 to equalize the array. Note that every step work with independent entries of $A$.

So yes equalization is the same as solving the change-making problem, and we don't need to worry about convergence between values because they are independent after the transformation.

Note that $\min A$ is not always the correct offset to subtract. For instance, the equalization problem is solvable with $A=\{0,1\}$ and $D=\{3,4\}$ but the change-making problem can be solved only with an offset of $-3$.