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)→(|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 (a1,a2,…,an) 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)→(|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 (a1,a2,…,an) 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