Puzzle time - subtracting around the corner

[jon-nyc]

Write down four integers between 0 and 100, in a horizontal line. Now perform the following operation: Compute the (absolute) difference between the first and second, and write it under the first; then write the difference between the second and third under the second; then the difference between the third and the fourth, under the third; finally, the difference between the fourth and the first, under the fourth. You now have a new line of four integers, still between 0 and 100.

Example: If you start with 41 22 6 93, your new line will be 19 16 87 52.

If you repeat this operation you will eventually reach 0 0 0 0. (Why? Note that with five numbers instead of four, this might never happen.) Your score is the number of operations it takes to reach this sorry state.

For the example above, you end up with

41 22 6 93
19 16 87 52
3 71 35 33
68 36 2 30
32 34 28 38
2 6 10 6
4 4 4 4
0 0 0 0

for a score of 7 (pretty crummy).

What's the highest score you can achieve?

[Klaus]

Hm, doesn't sound so terribly hard.

I can improve the lower bound to 13:

click to show

21 8 1 45
13 7 44 24
6 37 20 11
31 17 9 5
14 8 4 26
6 4 22 12
2 18 10 6
16 8 4 4
8 4 0 12
4 4 12 4
0 8 8 0
8 0 8 0
8 8 8 8
0 0 0 0

[Klaus]

As for why you eventually reach 0 0 0 0:

click to show

Consider this sequence:

All numbers are 0
All differences between subsequent numbers are 0.
All differences between subsequent differences are 0.
...

This describes the properties of a sequence, working backwards from 0 0 0 0. Eventually, it includes all 4-tuples with numbers between 0 and 100 (but it would not in the case of 5-tuples, e.g. 0 1 0 1 0 loops).

The non-circularity follows from the set inclusion property of the sets in the sequence. For instance:

• (0,0,0,0) is contained in all of these sets.
• (4,4,4,4) is contained in all but the first sets.
• (2,6,10,6) is contained in all but the first two sets.

And so forth.

This precludes a cycle.

[jon-nyc]

HINT: What's happening to parity as you perform your operations?

[Klaus]

Ah, I see.

click to show

If we perform the operation on parities, we can see that all numbers turn even after at most 4 steps.

If we consider symmetry/rotation, these two sequences cover all possible cases.

EOEE
OOEE
EOEO
OOOO
EEEE

EOOO
OEEO
OEOE
OOOO
EEEE

How to continue from here?

Well, once all numbers are even, we consider the parity of all numbers divided by two.

By the same argument, we'll only get numbers divisible by 4 after the next round. Then only numbers divisible by 8. Since all numbers are <=100, we must eventually end up with 0 0 0 0, since these are the only numbers that are divisible by any number.