wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Doomed to be zeros
        
(Message started by: irrational on Oct 11^th, 2006, 3:20pm)

Title: Doomed to be zeros
Post by irrational on Oct 11^th, 2006, 3:20pm

Culled from another forum:

There are four arbitrary positive integers A, B, C and D. Let us denote by A1, B1, C1 and D1 the differences between A and B, B and C, C and D and D and A (it is meant that everytime we subtract a smaller number from a greater one). Then, proceeding from the numbers A1, B1, C1 and D1, we similarly form a 4-tuple of numbers A2, B2, C2 and D2 and so on. Prove that after the procedure has been repeated several times we must necessarily arrive at a 4-tuple of zeros.

For example:
Take A=2, B=4, C=3, D=4. Now subtract higher value from lower value, A1=2,B1=1, C1=1, D1=2. Again A2=1, B2=0, C2=1, D2=0. Again A3=1, B3=1, C3=1, D3=1. Again A4=0, B4=0, C4=0, D4=0.

Title: Re: Doomed to be zeros
Post by Barukh on Oct 18^th, 2006, 4:57am

[hide]powers of 2[/hide].

Title: Re: Doomed to be zeros
Post by rmsgrey on Oct 18^th, 2006, 5:13am

Personally, I'd put this in medium. All it took was some systematic thought once I'd had the initial insight:

Initial insight:
[hideb]Firstly, observe that the maximum value after each iteration cannot be greater than after the previous iteration.
Proof:
If A and B are between 0 and N, so too must A₁ be, since the largest difference between any two numbers in that range is N, achieved by taking the extremes.

From this, all we need to do is show that any non-zero maximum must eventually decrease:[/hideb]
Systematic thought:
[hideb]Since the maximum, N, can only remain constant if there is a pair of adjacent values which are 0 and N in some order, we only need to consider the cases where A=N, B=0 (symmetries will cover the rest):

Suppose C=D=N. The sequence then goes:
N,0,N,N; N,N,0,0; 0,N,0,N; N,N,N,N; 0,0,0,0
At which point the maximum has decreased.

With C=D=0, we get:
N,0,0,0; N,0,0,N
which is equivalent to N,N,0,0 and we know that decreases.

The two sequences between them cover every situation where the only values are 0 and N, so any non-decreasing maximum must be found by including an intermediate value or two.

With C and D both intermediates:
N,0,C,D; N,C,C₁,D₁
(C₁ may be 0 if C=D, but neither C nor D₁ are, so there is no longer a 0 adjacent to an N)

With C=0:
N,0,0,D; N,0,D,D₁
Which is the previous case.

With C=N:
N,0,N,D; N,N,C₁,C₁
No longer any 0's

With D=0:
N,0,C,0; N,C,C,N

With D=N:
N,0,C,N; N,C,C₁,0
Which is the same as N,0,C,D

So in every case, a non-zero maximum must decrease after a bounded number of iterations (at most 4). Since the maximum can take at most N possible non-zero values, after 4N iterations, the maximum must have collapsed to 0 (in fact it will be (much) faster in most cases since the only situation where the maximum hasn't collapsed after 3 iterations collapses to 0 immediately after the 4th)[/hideb]

Follow-up question: what initial configuration takes longest to reach all 0's? And how long does it take? (if necessary, answers can be expressed in terms of parameters)

Title: Re: Doomed to be zeros
Post by Barukh on Oct 18^th, 2006, 5:51am

rmsgrey, for what number of arbitrary integers your argument still holds?

Title: Re: Doomed to be zeros
Post by towr on Oct 18^th, 2006, 6:02am

on 10/18/06 at 05:51:53, Barukh wrote:

rmsgrey, for what number of arbitrary integers your argument still holds?

It doesn't hold for 3 NN0 -> 0NN -> N0N -> NN0
Reminds me of Conway's game of life, certainly for larger tuples..

Title: Re: Doomed to be zeros
Post by jollytall on Oct 18^th, 2006, 7:05am

I guess Barukh's answer is based on the same thoughts as mine (although not too detailed :-)):

[hide]If all the four numbers have a common divider (A=ax, B=bx, etc.) then it is enough to prove that a,b,c,d gets down to all 0-s.
In the next step it is enough to prove that after a finite number of moves all numbers have a common divider. Actually it is a stricter (but easier to prove) statement that after a finite number of moves all numbers are even (i.e. 2 is the common divider).

If one number is odd and the rest are even (OEEE) then the next step is OEEO.
If three are odd (OOOE) then the next is again EEOO.
If two neighbouring are odd (OOEE) then the next one is EOEO.
If two opposites are odd (OEOE) then the next is OOOO.
If all are odd then the next step is OK.
If all are even then we are there.

I.e. in four steps maximum, all numbers are even, so we can divide all numbers by 2 and we get an equivalent problem.

The largest number cannot increase. (It can remain the same, unless we use rmsgrey's proof). But in max every 4th step we can divide by 2. So worst come worst the maximum number of moves is approx 4*log(2)N. In reality the number is much less, since
- the maximum number also decreases (see the a.m. proof),
- the four steps for halving is a maximum, in reality it is less, and
- any other common diveder does the trick.[/hide]

Title: Re: Doomed to be zeros
Post by towr on Oct 18^th, 2006, 8:29am

Aside from dividing/multiplying all numbers by a common divisor, you can also subtract/add the same amount from each number to get an equivalent problem.

Title: Re: Doomed to be zeros
Post by jollytall on Oct 19^th, 2006, 12:37am

A quick analysis suggests that it works iff N=[hide]2^n[/hide]. Proof to come (I hope).

Title: Re: Doomed to be zeros
Post by Miles on Oct 19^th, 2006, 2:13am

on 10/18/06 at 05:13:22, rmsgrey wrote:

Follow-up question: what initial configuration takes longest to reach all 0's? And how long does it take? (if necessary, answers can be expressed in terms of parameters)

The best I can find (but only by trial and error) is (1, 4, 8, 16) which takes 9 iterations to reach zero. It's simple to see that this quadruple is "locally" maximal (ie there is no quadruple that can be iterated to produce this quadruple), but is there a better solution?

Title: Re: Doomed to be zeros
Post by jollytall on Oct 19^th, 2006, 2:53am

I don't think that is correct. With few random runs I immediately found much longer ones. E.g.:
613849 323786 59378 244531 31169 360373 579936 941520
takes 23 steps to eliminate.

Another observation. Every N that does not reach all 0-s, will end up in only two different numbers, one of them is 0 the othejr is A>0. Proof needed though.

If that is true, I have the proof that N=2k+1 does not work:
If we start with any combination, of 0-s and A-s, in the first step we will have even number of A-s, because within a single block of A-s and a single block of 0-s, inside all numbers will be 0-s, while the "phase changes" will give A-s. The number of phase-changes is always even in the ring. But in order to reach only 0-s, the previous step must be all A-s. That is contradiction, knowing that N is odd, and the number of A-s (#A) is even.

Title: Re: Doomed to be zeros
Post by towr on Oct 19^th, 2006, 3:26am

on 10/19/06 at 02:53:24, jollytall wrote:

If that is true, I have the proof that N=2k+1 does not work <...>

Well, if that is true, I have a proof m*(2k+1) doesn't work. in which case only 2ⁿ are left.
Quite simply because the difference is calculated in a cyclic manner, so nothing really changes if you repeat the same tuple any number of times (because the resulting tuple is at every point locally identical to a point in the original tuple and hence behaves the same way there).

Title: Re: Doomed to be zeros
Post by Miles on Oct 19^th, 2006, 4:12am

on 10/19/06 at 02:53:24, jollytall wrote:

I don't think that is correct. With few random runs I immediately found much longer ones. E.g.:
613849 323786 59378 244531 31169 360373 579936 941520
takes 23 steps to eliminate.

Well, I was only using pencil and paper, but if you want to up the firepower, then sticking to 4 numbers (which I presumed in my previous post) randomly searching numbers less than 10million, I find 7510518, 8547540, 2099219, 5606352 takes 16 steps.

Not surprisingly, good solutions involve some big prime factors - 2099219 is prime, and the first number has a prime factor of 417251.

Clearly, the bigger the numbers the more steps are possible. Is it possible to prove that 16 steps is best below 10million (or improve on the earlier upper bound of 4*log(N)/log(2) which gives 93 for N = 10million)?

Title: Re: Doomed to be zeros
Post by jollytall on Oct 19^th, 2006, 4:28am

I think I have the missing linkfor the A>B>C>D>...>0 problem mentioned earlier.

Let's take any non A piece (X).
If any (or both) of its neighbours is A, then the new number in between them is less than A. The "less than A front" moved half a position ahead in that direction.
If any (or both) of its neighbours is another number Y<A, then again the new number in that direction is less than A.
If any (or both) of its neighbours is 0, then the new number is X again, i.e. the less than A front moved again ahead half a position.
If any (or both) of its neighbours of X is X, then the new number will be 0, but the next number follows one of the above logics, i.e. the less than A front moves ahead by 1.5 (or 2.5, 3.5, etc.) position.

Conclusion, the small number slowly eats up all the numbers ahead, until the two directions meet. With other words if in the ring A and B exists, where A>B>0 then A will surely disappear.

Consequence 1: in every steady (periodic) end state only 0 and A can exist.
Consequence 2: Based on my previous posting if N=2k+1 then can be a combination that gets periodic.
Consequence 3: Based on towr's solution, it also means that for every N<>2^n we can find a periodic non-solution.

Open questions:
Prove that any starting sequence for N=2^n gets down to all 0-s.
Find a better estimate for the number of steps than my very high limit of 4*upperrounding(log(2)A), where A is the highest number in the original set of N=4 elements.
Find an upper limit for other N-s.

Title: Re: Doomed to be zeros
Post by towr on Oct 19^th, 2006, 4:40am

on 10/19/06 at 04:12:08, Miles wrote:

My best so far, searching systematically, is
81 230 504 0 , which should take 19 steps, unless I've made a mistake.
Note that you can always have a 0, because as I mentioned before, subtraction/adding and multiplying/divisions leaves an equivalent problem. So in particular you can subtract the lowest number in the tuple from all elements.

Quote:

Is it possible to prove that 16 steps is best below 10million

No, because it isn't true :P

Title: Re: Doomed to be zeros
Post by jollytall on Oct 19^th, 2006, 5:14am

Towr,

How did you find that (other than brute force)? It is a rarely high iteration number, not significantly smaller than my theoretical number. For a high of 504, my limit is 4*9=36. 19 is more than half of it.
In terms of ratio, the best (or worst if you wish) I could find was 0,1,2,4 needing 7 steps hardly less than the theoretical 4*2=8.

If N>4, then even my limit does not stand. Using again elements in the form of 2^k, I get 0,1,2,4,8,16,32,64. 4*log(2)64=24, while it needs 26 steps to eliminate all numbers.

Title: Re: Doomed to be zeros
Post by towr on Oct 19^th, 2006, 5:24am

on 10/19/06 at 05:14:23, jollytall wrote:

How did you find that (other than brute force)?

What I did was probably worse than brute force. I worked backwards. starting at [0,0,0,0] to see what would lead there, then what would lead there, etc. it has a branching factor of 8, and then you still need to find an appropriate start-value (to add/subtract the differences from). It quickly becomes slow.
All things considered, brute force would be quicker, especially considering you only need 3 integers. so anything with only numbers under a 1000 would be in the order of a billion tries. That's, what, a second computation? My program takes a fair bit longer :P

I'm busy examining if there's a way to get arbitrary length runs though. (But that would go way past what the optimal one given a limit is).

[edit](brute force search up to 2000, assuming a>b>c>0)
22: 1705 778 274 0 [/edit]

Title: Re: Doomed to be zeros
Post by SMQ on Oct 19^th, 2006, 6:34am

For iterations > 12 it would appear an optimal solution is always of the form a, b:2b<a<3b, c:2c<b<3c, 0. Brute-force searching only that space gives the next few leaders as:

23: 4063, 1854, 653, 0
24: 4841, 2209, 778, 0
25: 5768, 2632, 927, 0
26: 13745, 6272, 2209, 0
27: 16377, 7473, 2632, 0
28: 19513, 8904, 3136, 0

Which seems to be approaching a = ~2.19149 * b, b = ~2.83929 * c with a high degree of precision.

--SMQ

Title: Re: Doomed to be zeros
Post by Barukh on Oct 19^th, 2006, 6:44am

In SMQ's examples, it is interesting to analyze the function F(n), whiich equals the first iteration when all the differences are 0 mod 2ⁿ.

The last one, for instance, has F(n) = 4 + 3(n-1) for n = 1, ..., 9.

Whereas the theoretical maximum gives F(n) = 4 + 4(n-1) for n = 1, ..., 16.

Title: Re: Doomed to be zeros
Post by SMQ on Oct 19^th, 2006, 7:16am

Well then, here's some more examples for ya. :)

29: 46499, 21218, 7473, 0
30: 55403, 25281, 8904, 0
31: 66012, 30122, 10609, 0
32: 157305, 71780, 25281, 0
33: 187427, 85525, 30122, 0
34: 223317, 101902, 35890, 0
35: 532159, 242830, 85525, 0
36: 634061, 289329, 101902, 0
37: 755476, 344732, 121415, 0
38: 1800281, 821488, 289329, 0
39: 2145013, 978793, 344732, 0
40: 2555757, 1166220, 410744, 0
41: 6090307, 2779074, 978793, 0
42: 7256527, 3311233, 1166220, 0
43: 8646064, 3945294, 1389537, 0
44: 20603361, 9401540, 3311233, 0
45: 24548655, 11201821, 3945294, 0
46: 29249425, 13346834, 4700770, 0
47: 69700671, 31805182, 11201821, 0
48: 83047505, 37895489, 13346834, 0
49: 98950096, 45152016, 15902591, 0
50: 235795681, 107596160, 37895489, 0
51: 280947697, 128199521, 45152016, 0
52: 334745777, 152748176, 53798080, 0
53: 797691075, 363995202, 128199521, 0
54: 950439251, 433695873, 152748176, 0
55: 1132436852, 516743378, 181997601, 0

Since a/b and b/c appear to converge to fixed ratios for the iteration leaders, I've refined my program to only search candidates with ratios within the maximum excursions of the last five its found.

[edit]
56: 2698569577, 1231386948, 433695873, 0
57: 3215312955, 1467182629, 516743378, 0
58: 3831006429, 1748130326, 615693474, 0
59: 9129195487, 4165752206, 1467182629, 0
60: 10877325813, 4963443281, 1748130326, 0
[/edit]

--SMQ

Title: Re: Doomed to be zeros
Post by towr on Oct 19^th, 2006, 7:40am

given [a,b,c,0] with a>b+c
then
[3a-b-c, 2a-2b,a-b-c, 0]
converges in one step more. And as it has the same property you have an infinite ascension to create however long a sequence you want.

There is also another class I'm still looking into.

[e] note that SMQ's solutions all conform to this same form, so you can use any of them to get a step higher[/e]

Title: Re: Doomed to be zeros
Post by Miles on Oct 19^th, 2006, 7:44am

You beat me to it :-/ - I was working on a similar approach and worked back to get
64: 0
7,046,319,384
20,006,521,300
43,844,049,029

Title: Re: Doomed to be zeros
Post by Miles on Oct 19^th, 2006, 7:46am

Sorry - that's one solution with the 4 numbers spread over 4 lines.

Title: Re: Doomed to be zeros
Post by Miles on Oct 19^th, 2006, 7:57am

on 10/19/06 at 07:40:13, towr wrote:

given [a,b,c,0] with a>b+c
then
[3a-b-c, 2a-2b,a-b-c, 0]
converges in one step more. And as it has the same property you have an infinite ascension to create however long a sequence you want.

But if we keep applying your rule, the first term more than doubles at each time, so the solutions become unwieldy. My approach which generates SMQ's results is as follows.

Consider the quadruple (0, x, 0, x). This will iterate in 2 steps to zero. Define the following sequence:

a(1) = 0, b(1) = x, c(1) = 0, d(1) = x

and

a(n+1) = [c(n) – a(n)]/2
b(n+1) = [c(n) + a(n)]/2
c(n+1) = [c(n) + a(n)]/2 + b(n)
d(n+1) = [3*c(n) + a(n)]/2 + b(n).

Note that d(n) = a(n) + b(n) + c(n).

If we apply the iterative rule to
(a(n+1), b(n+1), c(n+1), d(n+1))
then we get

(a(n), b(n), c(n), a(n) + b(n) + c(n))
which is just

(a(n), b(n), c(n), d(n)).
We need the condition that a(n), b(n) and c(n) are >=0
which can be proved fairly easily with a bit of induction.

So, the sequence reverses the iteration, and so (a(n), b(n), c(n), d(n)) will iterate to zero in n+1 steps.

Choosing x = 64, we get a(21) = 326.5, b(21) = 600.5, c(21) = 1104.5, d(21) = 2031.5, which applying a towr translation can be published as (0, 274, 778, 1705) – and of course towr has published that solution. In fact, I got the above method by looking at what happens when iterating towr’s solution – it is a case where if you start with the numbers in ascending order, the numbers in each following step are also in ascending order. Variations of my method could be considered by not making this a requirement.

The next quadruple in the sequence doesn’t publish to a whole number, but by doubling x, my method leads to (0, 927, 2632, 5768 ) which gets to zero in 25 steps. You can get SMQ’s 55 step solution by setting x = 2^17, and I got my 64 step solution with x = 2^20. So the only brute force is choosing k big enough that 2^k leads to an integer solution that takes whatever number of steps you require.

Title: Re: Doomed to be zeros
Post by towr on Oct 19^th, 2006, 8:07am

on 10/19/06 at 07:57:57, Miles wrote:

But if we keep applying your rule, the first term more than doubles at each time, so the solutions become unwieldy.

True, but it clearly shows that there exist problems of arbitrary length. Which was the quest I had set out on :P
There's still the question of how close an upper bound you can find.

Title: Re: Doomed to be zeros
Post by Miles on Oct 19^th, 2006, 8:25am

Yes, I'm too practical to be a really good mathematician. While others want to prove existence and bounds (which I find interesting), I'm more curious to actually generate an example (preferably longer than anyone else's!)

Title: Re: Doomed to be zeros
Post by towr on Oct 19^th, 2006, 8:50am

Well, either of our iterations can give an example of arbitrary length. So there's not much sport in finding the longest example anymore

It'd be interesting to find one that takes longer than 2*log₂(max) iteration steps (or prove there can't be)

[edit]Well, there's 7,3,1,0 which takes 7. But it'd be interesting if there was one with significantly higher numbers that also did it.[/edit]

Title: Re: Doomed to be zeros
Post by SMQ on Oct 19^th, 2006, 9:31am

Using a slight variation of Miles method which eliminates the guessing of x, I'm now generating a sequence which agrees 100% with what we seem to believe are the iteration leaders:

Start with a(2) = 0, b(2) = 1, c(2) = 0, d(2) = 1

Let (these are each 2*Miles step)
x(n+1) = c(n) - a(n),
y(n+1) = c(n) + a(n),
z(n+1) = c(n) + a(n) + 2b(n).

Now let
a(n+1) = x(n+1) / GCD(x(n+1), y(n+1), z(n+1)),
b(n+1) = y(n+1) / GCD(x(n+1), y(n+1), z(n+1)),
c(n+1) = z(n+1) / GCD(x(n+1), y(n+1), z(n+1)),
d(n+1) = a(n+1) + b(n+1) + c(n+1).

To find the leader for n iterations, let
i = d(n) - a(n),
j = c(n) - a(n),
k = b(n) - a(n),

and the leader is the quadruple { i / GCD(i,j,k), j / GCD(i,j,k), k / GCD(i,j,k), 0 }.

[edit]Note: you don't actually need the division by GCD in the recursion step -- it just helps keep the size of the numbers more managable. (You do need it in the "display" step, though.)[/edit]

--SMQ

P.S. 1000:
60,696,463,696,609,488,453,842,426,467,743,141,965,388,286,002,754,450,313,498,917,885,666,598,812,677,859,684,420,272,762,958,046,261,769,691,538,031,294,152,105,506,080,714,260,233,698,765,249,966,960,314,804,089,675,880,977,143,341
27,696,463,275,499,420,171,180,388,442,148,913,766,156,570,687,620,576,298,166,409,382,052,837,819,779,628,653,408,223,124,883,799,089,754,494,213,792,905,121,064,655,972,387,329,367,582,054,702,475,125,382,649,583,488,142,363,249,356
9,754,725,627,707,982,980,048,757,310,730,013,633,685,663,558,605,153,060,576,741,037,321,883,961,640,694,881,916,948,937,656,591,940,050,430,209,083,885,768,258,022,734,270,937,179,112,852,735,911,298,241,488,703,192,907,047,112,824
0
;D

Title: Re: Doomed to be zeros
Post by Miles on Oct 19^th, 2006, 9:38am

What a shame. I'm away from a PC for the next week, so won't be able to see how this develops. Maybe I'll work it all out myself on paper, or maybe not. And maybe you'll have all moved on by then...

Title: Re: Doomed to be zeros
Post by jollytall on Oct 19^th, 2006, 11:34am

While you were hunting for long sequences I still owe you the proof that N=2^n has always got a finite number of steps (although by now we all take it granted).
So:

Step 1: I have proved that in finite numbers any N gets down to a set that consist only of 0-s and one other number (A).

Step 2. For the sake of simplicity I use 0 and 1 only, although A can be any number.

Step 3. In any iteration a number is the parity of the two neighbours in the previous step (00 - 0, 01 -1, 10 -1, 11 - 0). It is actually the same as the parity of the total of the two neighbours.

Step 4. I want to check how any number of the original sequence contributes to the next and all following sequences.
Let's take the sequence: xxxxAxxxxx where x is undifined. If A is 0, in all following totals its contribution is still 0, i.e. it does not change the parity of any numbers in the future sequences. If A is 1, then its contribution (mod 2) to the following sequences is as follows:
Seq 0: xxxxxxxxxx1xxxxxxxx
Seq 1: xxxxxxxxx11xxxxxxxx
Seq 2: xxxxxxxx101xxxxxxxx
Seq 3: xxxxxxx1111xxxxxxxx
Seq 4: xxxxxx10001xxxxxxxx
Seq 5: xxxxx110011xxxxxxxx
Seq 6: xxxx1010101xxxxxxxx
Seq 7: xxx11111111xxxxxxxx
It can be seen that in steps 2^k -1 a sequence of 2^k pieces of 1s are generated. If the total ring is 2^k long then in the next step we get all 0s as a contribution. With other words if N=2^k then regardless the starting situation of 0-s and 1-s in step N we get all 0-s.

I.e. together with the earlier partial results we can say that it gets down to all 0-s if and only if N=2^k.

Title: Re: Doomed to be zeros
Post by towr on Oct 19^th, 2006, 12:21pm

And once you've remove any contribution mod 2, you can as it were divide the whole tupple by two and repeat (to remove the next bit's contribution)
So a general upper bound of log₂(max)*2^k ?

Title: Re: Doomed to be zeros
Post by SWF on Oct 19^th, 2006, 4:24pm

If a=( 5 - cbrt(19 - 3*sqrt(33)) - cbrt(19 + 3*sqrt(33)) )/3 = 0.160713...
and b=( 4 - cbrt(17 - 3*sqrt(33)) - cbrt(17 + 3*sqrt(33)) )/3 = 0.456311...

(cbrt(x)= cube root of x)

Choose four numbers of the form 0, a*N, b*N, N (all rounded to nearest integer), and you should be able to increase the number of steps as much as you want if N is large enough. To maximize number of steps N should be chosen so that a*N and b*N are both close to integers. This approach works because after each step and subtracting the lowest value as towr suggests to zero out the first number, the numbers remain in approximately the same ratio. If the starting values weren't rounded to integers the same ratio would be maintained, while the values decrease at each step.

Title: Re: Doomed to be zeros
Post by jollytall on Oct 19^th, 2006, 11:31pm

Yes, Towr.
My understanding is also that since in every N (where N=2^k) steps you can divide the model by 2, the theoretical maximum is N*log(2)A, where A is the largest number in the initial set.
This is fully in line with my original estimate for N=4.

I am also thinking on the impact of the fact that in N steps the largest number surely disappears (eaten up by the small numbers). Unfortunately a new number of A-1 might appear, so it is not true, that in N steps the largest number would be max the original second largest. (It would be nice, giving another limit of A*N.)
So it gives something like N*upperround(log₂(A-N)), although not sure in it. It is also not a significant reduction, even if true.

Title: Re: Doomed to be zeros
Post by Aryabhatta on Oct 21^st, 2006, 2:44pm

This sounds familiar: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1099273123

Title: Re: Doomed to be zeros
Post by Barukh on Oct 22^nd, 2006, 1:26am

on 10/21/06 at 14:44:49, Aryabhatta wrote:

This sounds familiar: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1099273123

Wow! I completely forgot that I once contributed to this problem... Where have you been before, Aryabhatta? ;D

So, after refreshing my memory, here's an easy way to construct a sequence with length a multiple of 3:

0, T_2k+1 - T_2k, T_2k+2 - T_2k, T_2k+3 - T_2k has length 3(k+1),
where T_k is the k-th Tribonacci number. Indeed, the quadruple (T_2k, T_2k+1, T_2k+2, T_2k+3) after 3k moves becomes (2^kT₀, 2^kT₁, 2^kT₂, 2^kT₃) = (0, 0, 2^k, 2^k), and it takes another 3 moves to get to all zeros.

The above solution coincides with SMQ's table for entries that are multiples of 3.

Title: Re: Doomed to be zeros
Post by Aryabhatta on Oct 23^rd, 2006, 10:44am

on 10/22/06 at 01:26:09, Barukh wrote:

Wow! I completely forgot that I once contributed to this problem... Where have you been before, Aryabhatta? ;D

I have been pretty busy with work lately... Thanks for asking ;D

Title: Re: Doomed to be zeros
Post by Sameer on Oct 23^rd, 2006, 10:54am

Welcome back Aryabhatta... another name to cross off!! :D

Title: Re: Doomed to be zeros
Post by Aryabhatta on Oct 23^rd, 2006, 12:38pm

on 10/23/06 at 10:54:41, Sameer wrote:

Welcome back Aryabhatta... :D

Thanks :D

Title: Re: Doomed to be zeros
Post by Miles on Nov 2^nd, 2006, 7:14am

on 10/19/06 at 08:25:19, Miles wrote:

I guess my inner mathematician wouldn’t stay quiet after all, as this has been niggling away at me since I last posted. I’ve only thought about the 4-tuple case. I’ve proved that given that the largest number in the 4-tuple is N, an upper bound for the number of steps to zero is 4*log(N)+4, where (here’s the twist)

I’m taking logarithms to base 3 [log(x) should be taken as log₃(x) in all that follows].

Empirically, I’ve crunched through lots of cases, and it looks like the actual number of steps can’t be more than 3*log(N) + 4. (I even speculate whether it is e*log(N) + 4).

I could say more about my proof if I get the time. What I’ll say is that a maximal 4-tuple (ie one that takes the maximum possible steps to reach zero) takes the form
(N,0,k*N,(k+j)*N), where j,k are positive with k+j <= 1.
The really interesting region in the space of (j,k) values is where j >= k and 1-2k-j >=0, and I assume these apply...

After one step, the quadruple becomes
(N, N*k, N*j, N*(1-k-j))
which can be translated to
(N*(1-k), 0, N*(j-k), N*(1-2k-j)) [the conditions above ensure all of these are non-negative].
which can be expressed as
(N’, 0, k’ * N’, (k’ + j’) * N’) where N’ = N * (1-k), k’ = (j-k) / (1-k), [a little algebra...] j’ = (1-k-2j)/(1-k), ie after one step, the new quadruple is of the same form.

Dropping the requirement for the elements to be integers, the first question is what is the fixed point, ie for what value of (j,k) does the rule map (j,k) to itself, ie solve

k = (j – k) / (1-k)

j = (1 – k – 2j) / (1-k)
As a pointer, the solution is around (0.30, 0.16) but I’ve an exact solution in terms of radicals.

The closer your starting point to this fixed point, the more steps it takes to get to zero. All of SMQ’s solutions are of this nature.

Anyone like to try calculating the fixed point?

Title: Re: Doomed to be zeros
Post by Miles on Nov 2^nd, 2006, 7:23am

Recapping, start with the quadruple
(N, 0, k * N, (j+k) * N), with 0 <= j,k; k <= j; 1-2k-j >= 0.

After 4 steps, it can be shown that either the quadruple will reach zero in at most 4 more steps or the maximum number in the quadruple is 2*N/3. We already know that after 4 steps, all the elements are even, so the quadruple can be halved and the maximum reduces to N/3. So every 4 steps, the maximum element reduces to a third or less. This implies that the maximum number of steps to zero is of the form 4*log(N) + c, taking logs to base 3. Experimenting with small cases shows that c=4 covers it.

If the initial quadruple is not of the type defined above, then it can be shown that it cannot beat 2*N/3 in 4 steps (or if it does, it then falls to zero in at most another 4 steps).

Title: Re: Doomed to be zeros
Post by Barukh on Nov 2^nd, 2006, 9:08am

on 11/02/06 at 07:23:48, Miles wrote:

Recapping, start with the quadruple
(N, 0, k * N, (j+k) * N), with 0 <= j,k; k <= j; 1-2k-j >= 0.

Taking N=1431, k = 0.16, j = 0.30 (as indicated in your previous post), I get the quadraple (1431, 0, 228, 658), which collapses after 12 steps, whereas your formula predicts at least 25.

Compare this to (0, 230, 653,1431), with 21 steps.

Title: Re: Doomed to be zeros
Post by Miles on Nov 2^nd, 2006, 3:12pm

on 11/02/06 at 09:08:13, Barukh wrote:

... whereas your formula predicts at least 25.

No, my formula predicts at most 30.

Sorry, I think you’ve got things back to front. I’m stating the upper bound, which for your case would be 4*log(1431)+4 = 30, so I would expect the best choice to take 20-odd steps.

on 11/02/06 at 09:08:13, Barukh wrote:

Compare this to (0, 230, 653,1431), with 21 steps.

More precise values for the fixed point would be j = 0.295598 and k = 0.160713 which lead to (1431, 0, 229.98, 652.98) so I’m not surprised your choice performs so well – it must be the optimal choice for N=1431. Using j=0.30, k=0.16 I would expect to do much worse, as you have demonstrated.

In fact j = [hide](5 + cbrt(3 * sqrt(33) – 19) – cbrt(3 * sqrt(33) + 19) / 3 where cbrt is the cube root.[/hide]

Title: Re: Doomed to be zeros
Post by SWF on Nov 2^nd, 2006, 6:05pm

Miles, did you read my post from Oct 19? Compare to your fixed point values.

Title: Re: Doomed to be zeros
Post by Miles on Nov 2^nd, 2006, 11:15pm

on 11/02/06 at 18:05:49, SWF wrote:

Miles, did you read my post from Oct 19? Compare to your fixed point values.

Weird - I don't remember seeing that, but I've even used the same notation for cube root as you!

Oh well, my fixed points aren't as original as I thought. However, I don't think anyone's come up with my use of base 3 logs, although I daresay there's a website somewhere... ::)