Substracting around the corner

3 Dec 2011

Given a sequence of n numbers, a[1] a[2] ... a[n] Replace a[i] with |a[i] - a[i+1]| (if i == n, then with |a[n]-a[1]|) Repeat it until every element is 0. Prove that with n=5, it may go on forever. But with n=4, it always terminates.

Ok, the first thing I have noticed is that

The setting, which is one step from the termination is when every element is equal.

Let's try a simple case first:

1, 2, 3, 4 1, 1, 1, 3 0, 0, 0, 2 0, 0, 2, 2 0, 2, 0, 2 2, 2, 2, 2 0, 0, 0, 0

Now in order to get to the sequence of x, x, x, …, you must come from

a, b, a, b, ...

I can immediately see that if the sequence of a, b, a, b, .. have an odd number of elements, then it is not possible to reach (a-b), (a-b), (a-b)…

The examples are:

a, b, a a, b, a, b, a

Therefore, unless we start with a sequence in which all elements are equal, a sequence with an odd number of elements will never terminate. <3

Now we need to prove that, for n=4, it always terminate.

Ok, how the heck can we prove it?

Let's try another example:

1, 10, 3, 4 9, 7, 1, 3 2, 6, 2, 6 4, 4, 4, 4 0, 0, 0, 0 *

Wow, that converges too early. Let's try a wilder example:

1, 10, 100, 1000 9, 90, 900, 999 81, 810, 99, 990 729, 711, 891, 909 18, 180, 18, 180 *

Wow, that still converges fast. Let's try another example:

3, 7, 13, 23 4, 6, 10, 20 2, 4, 10, 16 2, 6, 6, 14 4, 0, 8, 12 4, 8, 4, 8 *

I still don't see any pattern. I can try working backward instead:

x, x, x, x a, b, a, b . a, (b+a), (2b+a), 2b ---> No, this is not ok a, (b+a), (2b+a), (b+a) ---> This is ok

We should generalize it:

Let's say w, x, y, z generates a,b,a,b. This means

|w-x| = a ---> (w-x) = a OR (x-w) = a |x-y| = b ---> (x-y) = b OR (y-x) = b |y-z| = a ---> (y-z) = a OR (z-y) = a |z-w| = b ---> (z-w) = b OR (w-z) = b

It does not give me any insight except for that there are 16 possibilities that are valid.

Probably, we should try from other angles. Let's try working forward:

a, b, c, d and a>b>c>d (a-b), (b-c), (c-d), (a-d) (a-2b+c), (b-2c+d), (a-c), (b-d) -- assume (a+c) > 2b and (b+d) > 2c (a-3b+3c+d), (a+b-c+d), (a-b-c+d), (a-3b+c+d) -- assume (a+d) > (b+c) (4b-3c), (2b), (2b-2c), (2c)

We eventually rule out a and d, though it does not give me any insight. Ok, let's look at a simple example:

0, b, 0, 0 b, b, 0, 0 0, b, 0, b b, b, b, b 0, 0, 0, 0 *

Here we see how b is moved around and eliminate itself by cancelling out. Let's look at another pattern.

a, 0, 0, 0 a, 0, 0, a a, 0, a, 0 a, a, a, a 0, 0, 0, 0

Now what if we combine them?

a, b, 0, 0 (a-b), b, 0, a (a-2b), b, a, b (a-3b), (a-b), (a-b), (a-3b) (Can be branched) (2b), 0, (2b), 0 0, 0, 0, 0 *

Another possibility is:

(3b-a), (a-b), (a-b), (3b-a) (4b-2a), 0, (4b-2a), 0 0, 0, 0, 0 *

Now a few patterns emerge:

[a, a, b, b] OR [b, a, a, b] will always terminate.

One more step before that is:

x, b, a, b because the next step is (x-b), (b-a), (b-a), (x-b).

Actually,

[x, b, a, b] (and its variants) will always terminate.

Now let's try:

a, b, c, 0 (a-b), (b-c), c, a (a-2b+c), (b-2c), (a-c), b (a-3b+3c), (a-b-c), (a-b-c), (a-3b+c)

No patterns emerge… ok, I give up.

Solution from the book

It claims that within 4 steps, all numbers will be even.

let's say we start with:

o, o, o, o (o stands for odd number) e, e, e, e *

Or

o, e, o, e o, o, o, o *

Or

o, e, o, o o, o, e, e e, o, e, o o, o, o, o *

Ok, now we have proven that it ends up in all even numbers. Now what?

We know that two even numbers' difference is always even.

When we magically considers numbers modulo 2, we have found that the sequence 1000, 1100, 1110, and 1111 and other combinations end up in 0000.

This means it will ends up in all even numbers and the numbers will only decrease. Therefore, for n=4, it will terminate.

On the other side, for n=5, we have a cycle, 11000, 01001, 11011, 01100 and it goes on. The numbers never end up in all even. Therefore, it won't terminate.

I am indeed stupid…

Give it a kudos