(|a-b|,|b-c|,|c-d|,|d-a|),Continue this process,Is it necessary that we will get (0,0,0,0) at the end of process?In how many steps?(|a-b| means absolute value of the difference between a and b)

[ December 23, 2003: Message edited by: Capablanca Kepler ]

MH

Happiness is doing what is right.

"I'm not back." - Bill Harding, *Twister*

MH

My longest time so far:

Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.

that is, the first element of the next step would be

| (|a-b|) - (|b-c|) |

and not

| (a-b) - (b-c)

for example:

if a>b>c>d

then |a-b| = a-b, |b-c|=b-c, |c-d|=c-d, |d-a|=a-d

if b>a>c>d

then |a-b| = b-a, |b-c|=b-c, |c-d|=c-d, |d-a|=a-d

....

same at each step below. a program will solve the program.

[ January 15, 2004: Message edited by: Dean Lee ]

systematically

|a-b|=a-b

|b-c|=b-c

|c-d|=c-d

|d-a|=a-d

(00) if a+c>2b, b+d>2c

| |a-b|-|b-c| |=a+c-2b,

| |b-c|-|c-d| |=b+d-2c,

| |c-d|-|d-a| |=a-c,

| |d-a|-|a-b| |=b-d

(000) if a+3c>3b+d

| | |a-b|-|b-c| | - | |b-c|-|c-d| | |=a+3c-3b-d

| | |b-c|-|c-d| | - | |c-d|-|d-a| | |=a+c-b-d

| | |c-d|-|d-a| | - | |d-a|-|a-b| | |=a+d-b-c

(0000) if a-b>b-c+b-d

| | |d-a|-|a-b| | - | |a-b|-|b-c| | |=a+d+c-3b

(0001) if a-b<b-c+b-d

| | |d-a|-|a-b| | - | |a-b|-|b-c| | |=3b-a-d-c

(00000)

2b-2c

2c-2d

2b-2c

2c-2d

(00010) if 2a+4c>6b

2b-2c

2c-2d

4b-2a-2d

2a+4c-6b

(00011) if 2a+4c<6b

2b-2c

2c-2d

4b-2a-2d

6b-2a-4c

(000000)

2b+2d-4c

2b+2d-4c

2b+2d-4c

2b+2d-4c

(0000000)

0

0

0

0

so, in one of the coditions, after 7 steps, you will get 4 same numbers: 0

the conditions are

1)a>b>c>d

2)a+c>2b, b+d>2c

3)a+3c>3b+d

4)a-b>b-c+b-d

Now let us follow another scenario:

(00010) if 2a+4c>6b

2b-2c

2c-2d

4b-2a-2d

2a+4c-6b

(000100) if 2a+2c+d>5b; a+3c>4b

2b+2d-4c

2c+2a-4b

4a+4c+2d-10b

2a+6c-8b

(0001000) if a+5c>5b+d

2a+6c-6b-2d

6b-2a-2c-2d

2a-2b-2c+2d

2a-10b+10c-2d

(0001001) if a+5c<5b+d

2a+6c-6b-2d

6b-2a-2c-2d

2a-2b-2c+2d

10b-10c+2d-2a

(00010000) a+c>3b; a+d>2b; 2b+d>3c

4a-12b+8c

4a-8b+4d

8b+4d-12c

4b-4c

(000100000)

4b+4d-8c

4a-16b+12c

4b+4d-8c

4a+12c-16b

(0001000000) if a+d>5b+5c; a+5c>5b+d

4a-20b+20c-4d

4a-20b+20c-4d

4a-20b+20c-4d

4a-20b+20c-4d

(00010000000)

0

0

0

0

it takes 11 steps to get 4 "0", the conditions are:

1)a>b>c>d

2)a+c>2b, b+d>2c

3)a+3c>3b+d

4)a+c+d>3b

5)a+2c>3b

6)2a+2c+d>5b; a+3c>4b

7)a+5c>5b+d

8)a+c>3b; a+d>2b; 2b+d>3c

9)a+d>5b+5c; a+5c>5b+d

[ January 15, 2004: Message edited by: Dean Lee ]

systematically

etc

ie (a,b,a,b) -> (|a-b|,|a-b|,|a-b|,|a-b|) -> (c,c,c,c)

It would also be useful to prove (a,b,c,d) -> (b,c,d,a) (commutitive) and (a,b,c,d) -> (d,c,b,a) (reflective) rules.

The only useful identity I haven't worked out so far is (a,a,b,c)

[ January 15, 2004: Message edited by: David O'Meara ]

[ January 15, 2004: Message edited by: Dean Lee ]

systematically

which you have proved above.

systematically

but your approach is too theoratical for me. in my approach, i think the only thing tricky is that as you recurse, you have to keep track all the conditions, and when you attempt to add new conditions, you have to make sure:

1) it is not redundant

2) it is not contrary to existing ones

systematically

Sheriff

Searching for the longest sequences possible, here are the best results I've found so far.

Using positive ints:

(1278803968, 583532544, 205520896, 0) -->

**28 steps**to (0, 0, 0, 0)

Using positive longs:

(8164210999759470592, 3725419181890338816, 1312096840887304192, 0) -->

**54 steps**to (0, 0, 0, 0)

And using BigInteger, I can generate a sequence that has any number of step you like. The only catch is, I need bigger and bigger numbers to do it. E.g.

1817259805347476915735490125212155904,

829235615973112320612610445538230272,

292057719936274949636267345975443456,

0

--> 100 steps to (0, 0, 0, 0)

and

93622369971645644338230883259672944794082414233030991664651359611110031360,

42720916075869326782257660804684375746580940126611282490388402611014336512,

15046354862683456706396778735761803830395538735325586923419259932264890368,

0

--> 200 steps to (0, 0, 0, 0)

I haven't been able to establish a formula relating max number of steps to max range of the integers used. That is, I can generate a sequence of n steps using numbers no larger than 6^n; that's an upper bound. But I have no definite proof that it's not possible to get a cycle of n with numbers considerably smaller than 6^n. This is just the result of one particular technique of generating long sequences; there may be much longer sequences available using smaller numbers.

I can say fairly definitely that if we include all

*rational*numbers, or all integers (unbounded) (rather than just integers within particular bounds) then there is

*no*maximum bound on the number of steps. Given any 4 rational numbers a, b, c, d, which have n cycles we can always find another set a', b', c', d' (bounded in [0, 1] if you like) which has n + 1 cycles. So we could also find another set a'', b'', c'', d'' with n + 2. By induction we can generate a set of 4 rational numbers with

*any*number of cycles desired.

I also experimented a bit with this problem using different numbers of integers. E.g. for three integers, it's quite easy to generate an infinite sequence:

1 0 0

1 0 1

1 1 0

0 1 1

1 0 1

1 1 0

0 1 1

1 0 1

...

In fact it's easy to find such infinite sequences for any number of integers

*except*a power of two. If you have 2 integers in a set (a, b), there are just two cycles:

1: (|a-b|, |a-b|)

2: (0, 0)

For 4, 8, 16 cycles - well as discussed previously, the sequences generally converge to zeroes pretty quickly, but there are oddball sequences that take longer. But the do always seem to converge eventually. I'm

*guessing*that for any set of 2^n integers, the number of steps is always finite. (No infinite sequences.) Alas though, no proof of this yet.

[ January 16, 2004: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

Originally posted by Capablanca Kepler:

Take any four integers a,b,c,d.So we have(a,b,c,d) now change this to

(|a-b|,|b-c|,|c-d|,|d-a|),Continue this process,Is it necessary that we will get (0,0,0,0) at the end of process?In how many steps?(|a-b| means absolute value of the difference between a and b)

[ December 23, 2003: Message edited by: Capablanca Kepler ]

the original question seems to be:

1) whether the result has to be 0;

2) how many step?

so i think using random number generation won't be the solution. You can't not try all the possible combination, therefore you can't prove the resut will always be 0, unless you find 4 numbers, which does not come out to be (0,0,0,0), then you disprove it.

my proposed solution is to systematically explore the configuration of four numbers (in term of distance between 4 starting numbers). hopefully, there is a limit for number of different configurations for our purpose, so we can find out whether the result will always be 0. Or there will be unlimited configuration, but we will be able to draw the conclusion.

i will use recursion algorithm, starting from step one, going through all possibility, it is easy to record the number of step and four number at each step. the tricky thing is to keep track all assumption made, and to make judgement based on past assumption, or to make new assumptions.

the way i want to do it:

1) the generalized form of any assumption is (let a,b,c,d be the four starting numbers):

Na*a+Nb*b+Nc*c+Nd*d >= 0

here Na, Nb, Nc, Nd are rational numbers.

so all the assumption made in past can be expressed in a matrix.

for example:

a>b =>

1*a+(-1)*b+0*c+0*d >=0

b>c =>

0*a+1*b+(-1)*c+0*d >=0

a+c<d => d-a-c>=0 =>

(-1)*a+0*b+(-1)*c+1*d>=0

the these three assumption can be expressed in a metrix:

| 1 -1 0 0 |

| 0 1 1 0 |

| -1 0 -1 1 |

or

| Vector_1 |

| Vector_2 |

| Vector_3 |

if f(a,b,c,d)>=0

then f(a,b,c,d) must be a combination of past assumption, please note, combination means:

Vector_f = sum(Ni*Vector_i)

Ni can only be 0 or positive, since multipling negative number changes the direction.

so now we know how to judge an expression based on the past assumptions, if an expression can not be expressed in a combination of past assumption, new assumption have to be made to proceed. then update the matrix.

these are the main ideas of the tricky part of my future program.

[ January 16, 2004: Message edited by: Dean Lee ]

systematically

Sheriff

**so i think using random number generation won't be the solution. You can't not try all the possible combination, therefore you can't prove the resut will always be 0, unless you find 4 numbers, which does not come out to be (0,0,0,0), then you disprove it.**

Agreed. You can however get useful information about behavior, which can help guide in the types of solutions you look for.

**the original question seems to be:**

1) whether the result has to be 0;

2) how many step?

1) whether the result has to be 0;

2) how many step?

And to answer the second part first, there is no limit to the number of steps that may be necessary, unless you limit the problem to integers within a particular finite range. No random numbers are necessary to prove this. Though they did help guide my thinking in the first place. As I found longer and longer sequences (using random numbers) I stopped thinking about how to possibly prove that there was a limit to the number of iterations required, and instead prove that there is no limit. The latter path proved far more productive.

Of course, once we switch over to talking only about a finite range of integers (e.g. using only positive ints) then it becomes theoretically possible to prove a limit computationally, simply by enumerating and testing all possible combinations of numbers. Though of course it could take a while to actually perform the computation. I'd certainly like to see a nice simple formula for a solution, rather than a very computationally intensive brute-force approach. But don't be too quick to discount empirical approaces, since there's no guarantee that proof-based techniques will actually yield a useful result. It certainly may though, and I'll await further developments with interest. Good luck...

"I'm not back." - Bill Harding, *Twister*

Originally posted by Jim Yingst:

I can say fairly definitely that if we include allrationalnumbers, or all integers (unbounded) (rather than just integers within particular bounds) then there isnomaximum bound on the number of steps. Given any 4 rational numbers a, b, c, d, which have n cycles we can always find another set a', b', c', d' (bounded in [0, 1] if you like) which has n + 1 cycles. So we could also find another set a'', b'', c'', d'' with n + 2. By induction we can generate a set of 4 rational numbers withanynumber of cycles desired.

I am not so sure about that.

assume you have four rational numbers: x1, x2, x3, x4, which take n steps to converge to (0,0,0,0). there may not exit y1, y2, y3, y4, that (y1,y2,y3,y4) converge to (x1,x2,x3,x4).

what happened is:

|y1-y2| = x1

|y2-y3| = x2

|y3-y4| = x3

|y4-y1| = x4

so first of all, x1, x2, x3, x4 all have to be >= 0.

if y1>=y2, y2>=y3, y3>=y4

then,

y1-y2=x1

y2-y3=x2

y3-y4=x3

y1-y4=x4

add first 3 equations together,

y1-y4=x1+x2+x3

so x1+x2+x3 = x4 must be true, otherwise, you can not find solution.

if y2>=y1, y1>=y3, y3>=y4

then,

y2-y1=x1

y2-y3=x2

y3-y4=x3

y1-y4=x4

then you have to have

x1+x4=x2+x3

to have solution.

.....

so there is restriction on (x1, x2, x3, x4). no just any 4 rational number.

i guess my point is: you can have any 4 rational numbers, they will converge to (0,0,0,0) (to be proved). but you may not always be able to "reverse engineering" them, so that is a hint to me: that there may be a upper limit for the number of steps to converge.

[ January 17, 2004: Message edited by: Dean Lee ]

systematically

Sheriff

**[Dean]: assume you have four rational numbers: x1, x2, x3, x4, which take n steps to converge to (0,0,0,0). there may not exit y1, y2, y3, y4, that (y1,y2,y3,y4) converge to (x1,x2,x3,x4).**

That's true. As a simple example, consider (1, 0, 0, 0), which converges to (0, 0, 0, 0) in 4 steps. There is no possible (y1, y2, y3, y4) which can transform to (1, 0, 0, 0). But that's OK, because the goal is to find a sequence that transforms to another sequence that has the same number of steps to 0 as (1, 0, 0, 0) did.

That is, if

(x1, x2, x3, x4)

converges in n steps, then there are a number of transformations which we can perform which will not change the fact that there convergence occurs in n steps. E.g. we can multiply all the numbers by a constant:

(mx1, mx2, mx3, mx4)

and we can add a constant

(mx1 + k, mx2 + k, mx3 + k, mx4 + k)

We can also reverse the order, or rotate the elements. The resulting set of numbers will still converge in n steps.

To see how this is useful, look again at

(1, 0, 0, 0)

Multiply by 2:

(2, 0, 0, 0)

Add 1:

(3, 1, 1, 1)

This still converges in 4 steps, same as (1, 0, 0, 0) did. But now we've got a set that we can find a (y1, y2, y3, y4) for:

(0, 3, 2, 1)

This sort of thing can actually be done with any set (x1, x2, x3, x4). It's a bit tricky to work out the details for all cases, but there's always some combination of transformations (mx + k, rotate, reverse) which can convert (x1, x2, x3, x4) to an equivalent form (equivalent in the sane of having the same number of steps to convergence) from which we can find a (y1, y2, y3, y4) with one more stpe to convergence.

By the way I did fib earlier when I said I have a "formula" to derive (y1, y2, y3, y4). It's more of an algorithm, with several formulas within. The initial form was a bit messy; I've been simplifying its presentation before I post if here.

[ January 17, 2004: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

Here is what I got:

assume we want to get (y1,y2,y3,y4) for (x1,x2,x3,x4), so that it takes 1 step for (y1,y2,y3,y4) to converge to (x1,x2,x3,x4), then, by definition,

|y1-y2| = x1

|y2-y3| = x2

|y3-y4| = x3

|y4-y1| = x4

take square on both side,

(y1-y2)^2 = x1^2

(y2-y3)^2 = x2^2

(y3-y4)^2 = x3^2

(y4-y1)^2 = x4^2

then

y1^2-2*y1*y2+y2^2 = x1^2 ....... (1)

y2^2-2*y2*y3+y3^2 = x2^2 ....... (2)

y3^2-2*y3*y4+y4^2 = x3^2 ....... (3)

y4^2-2*y4*y1+y1^2 = x4^2 ....... (4)

(1)-(2)+(3)-(4):

y2y3-y1y2+y1y4-y3y4=0.5*(x1^2+x3^2-x2^2-x4^2)

then,

(y3-y1)(y2-y4)=0.5*(x1^2+x3^2-x2^2-x4^2)

now let us make some simplification,

let y1=y4=0; y3=1, .......................(5)

then

y2=0.5*(x1^2+x3^2-x2^2-x4^2)

so the (y1,y2,y3,y4) we are looking for is:

(0, 1/2*(x1^2+x3^2-x2^2-x4^2) ,1,0)

yes, there are always many (y1,y2,y3,y4) for (x1,x2,x3,x4) (if all of x1,x2,x3,x4 are >=0). one of them is:

(0, 1/2*(x1^2+x3^2-x2^2-x4^2) ,1,0)

one thing i want to add is:

make sure (0, 1/2*(x1^2+x3^2-x2^2-x4^2) ,1,0) is not the same (x1,x2,x3,x4).

if they are the same, it is easy to get arround it, at (5), make sure they are not the same.

[ January 17, 2004: Message edited by: Dean Lee ]

systematically

Sheriff

x - 1 = 1

has one solution, x = 2. But if we square both sides, we get

x^2 - 2x + 1 = 1

x = 0, 2

When we square both sides of an equation we're obligated to check our solution(s) to see if they're still valid for the original equation. I fear this is a problem for your solution. E.g. if we start with

(x1, x2, x3, x4) = (1, 0, 0, 0)

and plug in

(y1, y2, y3, y4) = (0, 1/2*(x1^2+x3^2-x2^2-x4^2) ,1,0)

we get

(y1, y2, y3, y4) = (0, 1/2*(1+0-0-0), 1, 0) = (0, 1/2, 1, 0)

If we apply our transformation seqence to this we get:

0: (0, 1/2, 1, 0)

1: (1/2, 1/2, 1, 0) (Not our original (1, 0, 0, 0) or equivalent)

2: (0, 1/2, 1, 1/2)

3: (1/2, 1/2, 1/2, 1/2)

4: (0, 0, 0, 0)

Thus the "solution" (a) doesn't transform to the original (1, 0, 0, 0) and (b) still has only 4 steps to (0, 0, 0, 0), same as (1, 0, 0, 0) did. (a) isn't necessarily a problem, except that as I understand your solution you never replaced (x1, x2, x3, x4) with some equivalent (mx1 + k, mx2 + k, mx3 + k, mx4 + k) as I'd suggested, so it seems you should expect to still see the original (x1, x2, x3, x4) when you transform your solution.

I still say it's always possible to find a set for numbers with n+1 cycles, but I don't think your solution works.

"I'm not back." - Bill Harding, *Twister*

Originally posted by Jim Yingst:

One problem with squaring both sides of an equation is that you can create additional solutions that aren't solutions of the original equation. E.g.

x - 1 = 1

has one solution, x = 2. But if we square both sides, we get

x^2 - 2x + 1 = 1

x = 0, 2

When we square both sides of an equation we're obligated to check our solution(s) to see if they're still valid for the original equation.

i think square does not introduce problem in this case, because here we have equations with absolyte value.:

|y1-y2| = x1

|y2-y3| = x2

|y3-y4| = x3

|y4-y1| = x4

I fear this is a problem for your solution.

yes, there is a problem, i guess i was not careful.

at equation (5) of my last post,

let y1=y4=0; y3=1, .......................(5)

in fact i can not do that, it is contrary to initial condition:

|y1-y2| = x1 = 1

|y2-y3| = x2 = 0

|y3-y4| = x3 = 0

|y4-y1| = x4 = 0

in fact, if (x1,x2,x3,x4)=(1,0,0,0), then the initial condition contradict itsef. so maybe we should call it a deadend.

******************************************************************

however, everything so far is a guess,

it is highly likely that:

1) the result for any four rational numbers will converge to (0,0,0,0)

2) there is no upper limit on the steps required to converge

but there is no proof yet. once again, i think one of the best ways to prove them is to use recursion method described in my previous posts.

[ January 18, 2004: Message edited by: Dean Lee ]

systematically

How? I'm working with showing that the standard deviation of step n+1 is less than or equal to the standard deviation of step n. I believe the 'equals' case is where Jim shows an infinite series, proving this is not possible in our case would be a separate exercise.

The maths is a bit larger than I expected, lucky I'm on holidays.

On a side note, I was considering the possibility of an infinite series, and the solution reminded me of Conway's "Game of Life" with weightings. The "standard deviation" proof will remove these infinite series if it works.

For (a,b,c,d) the standard deviation is

sd1 = 1/4 * [ a^2 + b^2 +c ^2 + d^2 - 1/4 * (a+b+c+d)^2 ]

For a single case ( |x1-x2|, |x2-x3|, |x3-x4|, |x4-x1| ) and innitially assuming x1>x2>x3>x4 the standard devation is

sd2 = 1/4 * [ (x1-x2)^2 + (x2-x3)^2 + (x3-x4)^2 ]

The next step would be to show sd1>sd2 then have a look at the other combinations for x1>x2 etc, but I can't see how to show sd1>sd2 given the above.

I tried replacing (a+b+c+d) with 4m where m=min(a,b,c,d), but that didn't work. I'm currently looking at the cases where it may cause sd1<sd2. I also tried expanding various elements, but the terms start to get nasty.

In sd2, note that (x1-x2) is less than x1 and (x2-x3) is less than x2 etc. It

*looks*smaller, but how to prove it?

[ January 20, 2004: Message edited by: David O'Meara ]

MH

Sheriff

However, this will only work if it's always true that after 4 steps, the values will be multiples of 2. (I can see how this would extend to 4, 8, etc. every four steps, if 4 steps makes everything even.) Do you have some sort of proof that this is true? Or is it just a general observation?

"I'm not back." - Bill Harding, *Twister*

Sheriff

0: E O O O

1: O E E O

2: O E O E

3: O O O O

4: E E E E

(O E O O), (O O E O), (O O O E) are like (E O O O) above - 4 steps to (E E E E)

(E E O O), (O O E E), (E O O E) are like (O E E O) above - 3 steps to (E E E E)

(E O E O) is like (O E O E) above - 2 steps to (E E E E)

(O O O O) above is 1 step from (E E E E)

(E E E E) is 0 steps from (E E E E)

That's 12 of the possibilities. For the remaining 4:

0: E E E O

1: E E O O

2: E O E O

3: O O O O

4: E E E E

(E E O E), (E O E E), (O E E E) are like (E E E O) above - 4 steps to (E E E E)

So for all 16 possible arrangements of even and odd numbers, after 4 steps, all will be even. And after 4k steps, all numbers will be multiples of 2^k. So if initially all numbers have magnitude < 2^k, the series will converge in 4k steps. Excellent. I think the problem is essentially solved now.

[ January 21, 2004: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

It is sorta covered in the JavaRanch Style Guide. |