»  Solutions to puzzles in my VDARE.com monthly Diary

—————————

•  Solution

First, here is the solution posted by Dr Winkler to National Museum of Mathematics subscribers, 7/16/22.

The reason your number sequence dives so quickly down to 0 0 0 0 is that any odd-even pattern becomes all even after at most four operations. At that point you might as well cut every number in half; it won't change your score from that point.

It follows that if you don't cut your numbers in half when they all become even, any string of numbers that gives you a decent score will come down to a string of relatively high powers of two (e.g., 16 16 16 16) before it hits bottom. Thus, to construct a high-scoring sequence, we might want to begin with something like that and somehow proceed backwards.

How can we reverse the process? It helps to note that if we take signed differences from left to right instead of absolute differences, they sum to zero. In symbols, if the list of numbers is A B C D, then we've been computing |A-B|, |B-C|, |C-D|, and |D-A|; if we instead compute A-B, B-C, C-D, and D-A, we get numbers that add up to 0. It follows that either the largest of our four absolute differences is the sum of the other three, or the largest plus the smallest is the sum of the other two.

Once we have the signed differences, it's easy to take a backward step: start with 0, add the first difference, then the second, then the third (adding the fourth will get you back to 0). If some of the resulting numbers are negative, just add the same amount to each to boost them to any level you want.

Suppose that we've been working backwards and currently looking at a sequence containing, in some order, the numbers E, F, G, and H, where E is the smallest, F the next smallest, and H the largest (possibly with ties).

We need either H = E+F G or H+E = F+G to proceed. Adding or subtracting the same number from each of E, F, G, and H will not change their differences, so we are free to do that without messing up whatever we've done so far. But that won't change (H+E) - (F+G), so either H+E = F+G already holds or it never will. But if H and E+F+G are the same parity, adding (H-E-F-G)/2 to each number will get us to a position in which the largest number is the sum of the other three.

In summary, there could be as many as two or as few as zero ways to move backwards from a given list of four numbers. Proceeding in this manner, you will find that you can get a score of 13 (many ways, for example 0 7 20 44) but no more, if you are limited to whole numbers from 0 to 100.

(You might be surprised to learn that almost any sequence of four real numbers — for example, 1, pi, e, phi — also reduces eventually to 0, 0, 0, 0. If you allow for rotation, reflection, shifting up or down, and multiplying by non-zero factors, none of which changes the score, there is only one immortal sequence! Try to find it if you dare …)

[I heard this problem from a substitute math teacher in high school who told us that a prisoner of war kept himself busy by computing scores of random sequences. I learned later that the process is sometimes done in nested squares known as "diffie boxes."]

Thanks, Doc, but that left a lot of open questions for me. For instance: Why does the subtraction process with four integers always end with 0 0 0 0? That isn't the case with three integers, or five, or six. Is it only true for powers of two? (Yes, it works for two integers. First line: 47 10. Second line: 37 37. Third line: 0 0.)

I can prove that the four-integer chain does indeed become all even numbers after at most four cycles of subtraction. Thus:

First note that your string of four numbers is some combination of odd and even, from odd-odd-odd-odd to even-even-even-even. (Zero counts as even.) That first line in Dr Winkler's example is odd-even-even-odd. Replacing "odd" by binary digit 0 and "even" by binary digit 1, that is 0110, i.e. hexadecimal 6.

Every other line can likewise have its odd-even pattern represnted by a hexadecimal digit. The next line in the example is odd-even-odd-even, binary 0101, so hexadecimal 5. Subsequent lines are hexadecimal 0, F, F, F, F, and F. Hexadecimal F, remember, is binary 1111; so these rows are all even-even-even-even.

Generalizing: You start with some string of four integers whose odd-even pattern gane be reduced to a four-digit binary number, i.e. a one-digit hexadecimal number: one of the hexadecimal digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Now do the subtracting thing on your string of four integers. The resulting new string also has an odd-even pattern corresponding to some hexadecimal number. With one hexadecimal digit representing each possible odd-even combination, the subtraction maps 0123456789ABCDEF to FC9A30566503A9CF. Doing the subtraction thing a second time maps the possibilities to FA50AF0550FA05AF. A third time gets you to F00F0FF00FF0F00F and a fourth round results in FFFFFFFFFFFFFFFF.

So yes: Every possible odd-even combination of four integers ends up, after at most four subtraction cycles, as even-even-even-even.

That this will necessarily get you to 0 0 0 0 after some further cycles, I have not been able to prove.