This is a solution to the four numbers game puzzle.
Brief description:
Start with four integers $(a,b,c,d)$ and repeatedly apply the transformation $(a,b,c,d) \to (|a-b|, |b-c|, |c-d|, |d-a|)$ stopping only when all become zero.
Are there initial $(a,b,c,d)$ for which you will never stop?
Harder: Characterize all the $n$ such that repeated such transformations to $(a_1, a_2, \dots, a_n)$ will always stop irrespective of initial numbers.
Solution
The numbers will be non-negative after one step.
Now we can show that, eventually, all the numbers will be become even (try it out!).
Since $(2a,2b,2c,2d)$ stops iff $(a,b,c,d)$ stops, we can divide by two.
Thus, the maximum of the four numbers will decrease in a finite number of steps.
Thus the transformation will have to stop.
The harder version: The only such $n$ for which this works is powers of two. (I will leave the proof of this open, for the next blog post, here: http://ruffnsluff.blogspot.com/2015/10/four-number-game-ii-solution.html).
Brief description:
Start with four integers $(a,b,c,d)$ and repeatedly apply the transformation $(a,b,c,d) \to (|a-b|, |b-c|, |c-d|, |d-a|)$ stopping only when all become zero.
Are there initial $(a,b,c,d)$ for which you will never stop?
Harder: Characterize all the $n$ such that repeated such transformations to $(a_1, a_2, \dots, a_n)$ will always stop irrespective of initial numbers.
Solution
The numbers will be non-negative after one step.
Now we can show that, eventually, all the numbers will be become even (try it out!).
Since $(2a,2b,2c,2d)$ stops iff $(a,b,c,d)$ stops, we can divide by two.
Thus, the maximum of the four numbers will decrease in a finite number of steps.
Thus the transformation will have to stop.
The harder version: The only such $n$ for which this works is powers of two. (I will leave the proof of this open, for the next blog post, here: http://ruffnsluff.blogspot.com/2015/10/four-number-game-ii-solution.html).
No comments:
Post a Comment