Start with a vector (ordered quadruplet) of any four integers. Construct a new such vector that is the difference between successive elements of the first, cyclically so that the last difference is that between the last element of the first sequence and the first element of that array. Always take the absolute value when doing the differences. Call this the "diffy" operation.

If we repeat the diffy operation starting with the sequence (3, 7, 1022, 2005) we get the following.

(3, 7, 1022, 2005)
(4, 1015, 983, 2002)
(1011, 32, 1019, 1998)
(979, 987, 979, 987)
(8, 8, 8, 8)
(0, 0, 0, 0)

True or False: Any starting sequence of integers leads to the zero vector in finitely many steps. Offer proof.

Even if some of the initial integers are negative, after the first iteration they will all be non-negative since absolute values are being taken, so we can safely assume that all of the integers are >= 0.

If none of the elements at step n are zero then the largest element at step n+1 must be less than the largest number at step n. Why? Because no number in step n+1 can exceed the larger of the two (non-negative) predecessors being subtracted to make it, and cannot equal the larger of its two predecessors without a zero element being present.

If three of the elements at step n are zero, then the sequence ends after 4 steps:

0 0 0 a
0 0 a a
0 a 0 a
a a a a
0 0 0 0

If two of the elements at step n are zero and not adjacent, the sequence ends after 4 steps

0 a 0 b
a a b b
0 |a-b| 0 |a-b|
|a-b| |a-b| |a-b| |a-b|
0 0 0 0

If there are two adjacent zeros and two equal non-zeros at step n, the sequence ends 3 steps later:
0 0 a a
0 a 0 a
a a a a
0 0 0 0

If there are two adjacent zeros at step n and the two non-zero values are distinct, the sequence has only one zero the following step:

0 0 a b
0 a |a-b| b


If there is one zero at step n, there are no zeros in it at step n+1 if the step n values are all distinct.

0 a b c
a |a-b| |b-c| c UNLESS a=b or a=c or a=b=c

If a=b=c then the sequence terminates after 4 steps:

0 a a a
a 0 0 a
a 0 a 0
a a a a
0 0 0 0

If a=b or b=c but a != c, then after one step the sequence still has one zero BUT the value are all distinct UNLESS one value is exactly twice the other. But if this is the case, the sequence terminates after 4 steps:

0 a a c
a 0 |a-c| c if |a-c| != a and != c

-OR-
0 a a 2a
a 0 a 2a
a a a a
0 0 0 0 0

-OR-

0 2a 2a a
2a 0 a a
2a a 0 a
a a a a
0 0 0 0

Now, the maximum value in step n must be >= the maximum in step n+1, and can only be = if there is a zero in step n. But if there is a zero in step n then either there is NOT a zero in one or both of step n+1 and step n+2,  or the sequence will terminate.

Since every time a step has no zeros, the maximum value decreases in the next step, and since every time a step has zeros it does not increase the maximum step's value AND it either terminates in 4 steps or reaches a state with no zeros within 2 steps, the maximum value of a step must decrease at least every 3 steps. Since this maximum value can never fall below zero, then after a finite number of steps (equal to 3 times the largest initial number) the maximum value will be 0. And when that happens, since all values are >= 0 after step 1, all values must =0 and the sequence must have ended.

Posted by Paul on 2013-06-27 19:24:22