Author |
Topic: Doomed to be zeros (Read 2753 times) |
|
irrational
Junior Member
Gender: 
Posts: 52
|
 |
Doomed to be zeros
« on: Oct 11th, 2006, 3:20pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Doomed to be zeros
« Reply #1 on: Oct 18th, 2006, 4:57am » |
Quote Modify
|
powers of 2.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Doomed to be zeros
« Reply #2 on: Oct 18th, 2006, 5:13am » |
Quote Modify
|
Personally, I'd put this in medium. All it took was some systematic thought once I'd had the initial insight:
Initial insight:
| hidden: | 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 A1 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: |
Systematic thought:
| hidden: | 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,C1,D1
(C1 may be 0 if C=D, but neither C nor D1 are, so there is no longer a 0 adjacent to an N)
With C=0:
N,0,0,D; N,0,D,D1
Which is the previous case.
With C=N:
N,0,N,D; N,N,C1,C1
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,C1,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) |
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)
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Doomed to be zeros
« Reply #3 on: Oct 18th, 2006, 5:51am » |
Quote Modify
|
rmsgrey, for what number of arbitrary integers your argument still holds?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Doomed to be zeros
« Reply #4 on: Oct 18th, 2006, 6:02am » |
Quote Modify
|
on Oct 18th, 2006, 5:51am, 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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Doomed to be zeros
« Reply #5 on: Oct 18th, 2006, 7:05am » |
Quote Modify
|
I guess Barukh's answer is based on the same thoughts as mine (although not too detailed  ):
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Doomed to be zeros
« Reply #6 on: Oct 18th, 2006, 8:29am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Doomed to be zeros
« Reply #7 on: Oct 19th, 2006, 12:37am » |
Quote Modify
|
A quick analysis suggests that it works iff N=2^n. Proof to come (I hope).
|
|
IP Logged |
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Doomed to be zeros
« Reply #8 on: Oct 19th, 2006, 2:13am » |
Quote Modify
|
on Oct 18th, 2006, 5:13am, 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?
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Doomed to be zeros
« Reply #9 on: Oct 19th, 2006, 2:53am » |
Quote Modify
|
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.
|
| « Last Edit: Oct 19th, 2006, 2:54am by jollytall » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Doomed to be zeros
« Reply #10 on: Oct 19th, 2006, 3:26am » |
Quote Modify
|
on Oct 19th, 2006, 2:53am, 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 2n 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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Doomed to be zeros
« Reply #11 on: Oct 19th, 2006, 4:12am » |
Quote Modify
|
on Oct 19th, 2006, 2:53am, 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)?
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Doomed to be zeros
« Reply #12 on: Oct 19th, 2006, 4:28am » |
Quote Modify
|
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.
|
| « Last Edit: Oct 19th, 2006, 4:31am by jollytall » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Doomed to be zeros
« Reply #13 on: Oct 19th, 2006, 4:40am » |
Quote Modify
|
on Oct 19th, 2006, 4:12am, Miles wrote: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. |
|
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 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Doomed to be zeros
« Reply #14 on: Oct 19th, 2006, 5:14am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Doomed to be zeros
« Reply #15 on: Oct 19th, 2006, 5:24am » |
Quote Modify
|
on Oct 19th, 2006, 5:14am, 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
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]
|
| « Last Edit: Oct 19th, 2006, 5:43am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Doomed to be zeros
« Reply #16 on: Oct 19th, 2006, 6:34am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Doomed to be zeros
« Reply #17 on: Oct 19th, 2006, 6:44am » |
Quote Modify
|
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 2n.
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.
|
| « Last Edit: Oct 19th, 2006, 6:47am by Barukh » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Doomed to be zeros
« Reply #18 on: Oct 19th, 2006, 7:16am » |
Quote Modify
|
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
|
| « Last Edit: Oct 19th, 2006, 8:47am by SMQ » |
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Doomed to be zeros
« Reply #19 on: Oct 19th, 2006, 7:40am » |
Quote Modify
|
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]
|
| « Last Edit: Oct 19th, 2006, 7:41am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Doomed to be zeros
« Reply #20 on: Oct 19th, 2006, 7:44am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Doomed to be zeros
« Reply #21 on: Oct 19th, 2006, 7:46am » |
Quote Modify
|
Sorry - that's one solution with the 4 numbers spread over 4 lines.
|
|
IP Logged |
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Doomed to be zeros
« Reply #22 on: Oct 19th, 2006, 7:57am » |
Quote Modify
|
on Oct 19th, 2006, 7:40am, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Doomed to be zeros
« Reply #23 on: Oct 19th, 2006, 8:07am » |
Quote Modify
|
on Oct 19th, 2006, 7:57am, 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
There's still the question of how close an upper bound you can find.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Doomed to be zeros
« Reply #24 on: Oct 19th, 2006, 8:25am » |
Quote Modify
|
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!)
|
| « Last Edit: Oct 19th, 2006, 8:25am by Miles » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print