Puzzle time - flipping the pentagon
-
By the way, Horace, it isn’t even the case that the amount of negative amplitude never increases. Consider a negative between two zeros. Or between two negative numbers.
-
There’s something that invariably decreases, but I was unable to find and specify it in the time I put in.
-
That’s one of the first things I tried
-
Frustrating how many metrics almost always decreased.
(I had a python script that would generate the numbers randomly and iterate the steps, displaying each successive set and whatever metric I tried.)
-
Reminds me of cellular automata, famously explored by Stephen Wolfram.
At first I missed the "sum is positive" condition and was confused because when the sum isn't positive, the process doesn't terminate.
In fact, from what I can see, the sum of all numbers always stays the same, so of course if the sum is negative, at least one number must be negative.
My first idea would be to show that there is a number n, such that after n steps the number of negative labels has decreased by at least 1.
I also have the vague suspicion that the problem has some relation to Euclid's algorithm for greatest common divisor.
No time now, but I'll revisit the problem tomorrow.
-
Klaus - I intimated earlier the following hint:
Try to find some measure of progress; that is, some value that you can compute from the five numbers which either always goes up or always goes down, and won't stop moving until all the numbers are non-negative.
-
Yes, I saw that, but sometimes it’s easier to combine multiple small steps into a big step and show progress with regard to a decreasing well founded order for the big steps.
But I think I have an idea now.
:::
Consider the Infinite sequence of partial sums as you Walk around the Pentagon (just keep walking indefinitely).That sequence increases after at most 5 steps because the sum of the numbers is positive.
If all numbers are positive, it would be a sorted sequence.
I believe every flip makes this sequence “more sorted”, I.e. it decreases the number of sorting errors.
I’ll try to work out the details tomorrow but I’m positive this will work.
::: -
(sum of positive values) - (abs(sum of negative values)) will go up or remain constant. If constant, then the number of negative values is reduced. If the number of negative values goes up, it means that the metric goes up.
Edit: This should be the difference of absolute values rather than their ratio.
-
That’s just equal to the sum of the 5 numbers which remains constant by definition.
-
Got it.
:::
Let l-0 to l-4 be the label values.The partial sums are:
P-0 = 0
P-i = P-(i-1) + l-(i modulo 5)Obviously, for every i, P-(i+5) = P-i + s, where s is the sum of l-0 to l-4. So the sequence of P-i is
roughly sorted, but there are sorting errors in between.More precisely, let e-i be the number of sorting errors at i, defined as follows:
e-i = the number of j > i with P-j < P-i.
e-i is finite because the sum of labels is positive.
Now consider the sum of errors E = e-0 + ... + e-4.
Every flip decreases E by one, hence we are done after E steps.
Example with the "critical case" of a flip turning two positive numbers negative.
The error sum in the beginning is 5 and indeed we are done after 5 flips. We see how the error values 4 and 0 are swapped by the flip, but after the flip the 4 is decreased by one to 3. All other errors stay the same.
So my method also gives you the number of required flips. And it generalizes easily to more than 5 labels.
:::
-
Wait a minute.... try your theory on this set:
[3,-6,-1,-2,11] and flip the -6.
I think you'll find that the sum of the errors stays the same.
-
No, it works fine on your example.
The required number of flips decreases from 13 to 12 after flipping the -6.
Try it out and you'll see that you'll indeed need 13 flips for the example, which is exactly the sum of sorting errors predicted by my method.
In the general case, if you flip l-i, then the new e-i is the old e-(i+1) and the new e-(i+1) is the old e-i minus one: all other e-j stay the same. Hence the sum of e-0 to e-4 decreases by 1 with each flip.
-
Never flipped the Pentagon, but I’ve flipped off Capitol Hill.
-
I've implemented my method of calculating the number of required flips as a program.
You can execute the program and try it with different examples.
What you see is what it does to Jon's example.
Just press "Run".
-
I've also used the code to create examples that maximize the number of required flips.
For instance, within the range of numbers between -10 and +10, the examples
that are "maximal" with regard to required flips need 96 flips. Here's one such example:10, 10, 1, -10, -10
