StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POTurning an array of integers into an array of nonnegative integers
text
Body
copied!<p>Start with an array of integers so that the sum of the values is some positive integer <code>S</code>. The following routine always terminates in the same number of steps with the same results. Why is this?</p> <p>Start with an array <code>x = [x_0, x_1, ..., x_N-1]</code> such that all <code>x_i</code>'s are integers. While there is a negative entry, do the following:</p> <ul> <li><p>Choose any index <code>i</code> such that <code>x_i < 0</code>.</p></li> <li><p>Add <code>x_i</code> (a negative number) to <code>x_(i-1 % N)</code>.</p></li> <li><p>Add <code>x_i</code> (a negative number) to <code>x_(i+1 % N)</code>.</p></li> <li><p>Replace <code>x_i</code> with <code>-x_i</code> (a positive number).</p></li> </ul> <p>This process maintains the property that <code>x_0 + x_1 + ... + x_N-1 = S</code>. For any given starting array <code>x</code>, no matter which index is chosen at any step, the number of times one goes through these steps is the same as is the resulting vector. It is not even obvious (to me, at least) that this process terminates in finite time, let alone has this nice invariant property.</p> <p>EXAMPLE:</p> <p>Take <code>x = [4 , -1, -2]</code> and flipping <code>x_1</code> to start, the result is</p> <pre><code>[4, -1, -2] [3, 1, -3] [0, -2, 3] [-2, 2, 1] [2, 0, -1] [1, -1, 1] [0, 1, 0] </code></pre> <p>On the other hand, flipping <code>x_2</code> to start gives </p> <pre><code>[4, -1, -2] [2, -3, 2] [-1, 3, -1] [1, 2, -2] [-1, 0, 2] [1, -1, 1] [0, 1, 0] </code></pre> <p>and the final way give this solution with arrays reversed from the third on down if you choose <code>x_2</code> instead of <code>x_0</code> to flip at the third array. In all cases, 6 steps lead to <code>[0,1,0]</code>.</p> <p>I have an argument for why this is true, but it seems to me to be overly complicated (it has to do with <a href="http://en.wikipedia.org/wiki/Coxeter_group" rel="noreferrer">Coxeter groups</a>). Does anyone have a more direct way to think about why this happens? Even finding a reason why this should terminate would be great.</p> <p>Bonus points to anyone who finds a way to determine the number of steps for a given array (without going through the process).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload