| Consider the sum of the squares of the differences of of the values
of all non-touching nodes:
For: _A_
E B
\ /
D-C
We would have:
2 2 2 2 2
(A-C) +(C-E) +(E-B) +(B-D) +(D-A)
Call the value the Wumpus (or whatever...) of the Order pentagonal
set S = <A,B,C,D,E>.
2 2 2 2 2
Thus we can say W(S) = (A-C) +(C-E) +(E-B) +(B-D) +(D-A)
Now this reduces to: 2 2 2 2 2
2((A +B +C +D +E )-(AC+CE+EB+BD+DA)
Now:
1) If there are no negative values in S then we halt. Case
closed.
2) If there is some negative value in S (say its B) then we
could apply the operator to it:
A --> A+B
B --> -B
C --> C+B
The Wumpus of S1 is now:
2 2 2 2 2
2A +2B +2C +2D +2E -2AC-2CE-2EB-2BD-2DA
+4AB +4CB -2AB-2BE+4EB+4BD-2DB
2 2 -2CB
+2B +2B 2
-2B
Subtracting W(S) and reducing we find:
2
dW (S) = 2 (B + AB + CB + EB + BD)
= B * 2(A + B + C + D + E)
Now it is given that (A+B+C+D+E) is positive, and we choose
B because it was negative so dW must always be negative.
Thus W(S1) < W(S) for all valid S.
Clearly the wumpus of any set MUST be a positive integer, or
zero.
Since W(S) is some finite positive integer, and W(S+n) will
be ever decreasing, and since W(S+n) must still always be positive,
then S --> S1 --> S2 --> ... cannot continue infintely.
Therefore it must halt.
The flak may now ensue. B^)
-- Barry
|
| Newsgroups: net.math
Path: decwrl!glacier!navajo!avg
Subject: Re: for all you math wizzes out there (Berkeley included), a problem....
Posted: 3 Oct 86 07:45:13 GMT
Organization: Stanford University
Keywords: x,y,z
A lunchtime group of Stanford CS faculty and grads kicked this puzzle around
for an hour. I suggested looking for a function of the vertex values
that the operation drives toward zero, something like the
sum of the squares, except that the sum of squares does not work.
But after a few minutes, Ramsey Haddad thought of the following function,
A^2+...+E^2 + (A+B)^2 + (B+C)^2 + (C+D)^2 + (D+E)^2 + (E+A)^2
which DOES work.
If the operation is applied to C (which must be negative), the change
in the above function is 2C(A+B+C+D+E), which must be negative.
A nice feature of this is that it generalizes to larger polygons.
Don Knuth suggested looking at longer consecutive sums,
and later I worked out the following.
If n is odd, say 25, the function to look at is
A^2+ B^2 + ... + Y^2 +
(A+B)^2 + (B+C)^2 + ... + (Y+A)^2 +
(A+B+C)^2 + (B+C+D)^2 ... + (Y+A+B)^2 +
... +
(A+...+L)^2 + (B+...+M)^2 + ... + (Y+A+...+K)^2
i.e., all sums of 1 through (n-1)/2 consecutive values are
squared and summed. The operation applied to M produces a change
of 2C(A+...+Y).
If n is even, say 26, a slight variation is needed, as follows:
2 (A^2+ B^2 + ... + Z^2) +
(A+B)^2 + (B+C)^2 + ... + (Z+A)^2 +
(A+B+C)^2 + (B+C+D)^2 ... + (Z+A+B)^2 +
... +
(A+...+X)^2 + (B+...+Y)^2 + ... + (Z+A+...+W)^2
i.e., all sums of 2 through (n-2) consecutive values are
squared and summed, and twice the sum of individual squares is added.
The operation applied to M produces a change of 4M(A+...+Z).
Some students had already looked at the problem and developed
a termination proof along different lines. Also note that if the
sum of values is allowed to be 0, then 0 1 -1 1 -1 does not terminate.
My open question is, suppose the sum of the weights is negative?
|
| Suspecting that there is considerable latitude in chosing a W(S),
suppose that the transformation of x,y,z (where y is negative) is:
x+ay, y-(a+b)y, z+by
where a and b are arbitrary values (which may change for different
applications of the transformation) such that 0 < a,b <= 1.
Is Barry's W(S) still a decreasing function?
|
| Re .3
Well looks like I procrastinted too long on edp's suggestion. I'm
still trying to figure out how to modify my original note. Oh well
you know what they say: "Lucky at love, lousy at Notes." Or something
like that.
Re .4
Good question, but its too late for thinking right now, maybe
tommorrow. Or maybe some larger brains can kick it around. What
does Don Knuth have to say? ;^)
-- Barry
ps. Anybody who knows how, feel free to submit any/all of my replies
to the Usenet, if thats appropiate.
|