Puzzle time - flipping the pentagon
-
The vertices of a pentagon are labeled with integers, the sum of which is positive. At any time, you may change the sign of a negative label, but then the new value is subtracted from both neighbors' values so as to maintain the same sum.
For example, if (reading clockwise around the pentagon) the numbers are 1, 2, -2, -3, 3, you could flip the -2 and get 1, 0, 2, -5, 3 or you could flip the -3 and get 1, 2, -5, 3, 0.
Show that, inevitably, no matter which labels are flipped, the process will terminate after finitely many flips, with all values non-negative.
-
If you consider the energy of the system to be the sum of the negative values, you can see that a flip will at best conserve that energy while consolidating it into fewer vertices. For all other cases it will reduce that energy until it is zero, i.e. there are no negative numbers left.
-
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.
-
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.
:::
-
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.
