My kids' Honors Algebra I teacher used to pose this problem (the one with nonzero integers) at the beginning of the year. One can back up arbitrarily far, and I seem to remember that it's something like the Fibonocci sequence; there was even a reference on the Web, if I recall correctly. I'll look to see if we've saved any of that on my computers at home. Bill -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Joshua Zucker Sent: Saturday, December 11, 2010 2:44 PM To: math-fun Subject: [math-fun] Circle of differences I suspect this is well-known but I am still excited that I figured it out for myself last night. Start with four numbers written around a circle. At each moment, replace the four numbers with the absolute value of the difference of each adjacent pair. For example 1 9 4 7 would be replaced by 8 5 3 6 and then 3 2 3 2 and then 1 1 1 1 and then 0 0 0 0 and thereafter it's pretty boring. The problem: 1) Prove that given any four integers, it eventually reaches 0 0 0 0. (I had seen this result before). Also give a reasonable upper bound relating the size of the largest integer to the number of steps to reach 0 0 0 0. (A a reasonable bound that at least has the right proportionality in big O terms but maybe with a slightly too generous constant by a factor of 2 or so). 2) Prove that there exist lists of four integers that take as many steps as you want to reach 0 0 0 0. Let's make it a constructive proof that actually gives an algorithm for constructing a set of integers that, say, lasts 1000 steps. 3) What happens if you start with irrationals? Say, things of the form a + b sqrt(2)? Does it still always reach 0 0 0 0 for them? 4) Prove that there exists a list of four irrationals that never reach 0 0 0 0. Last night I solved 2 and 4 and that made me happy. I have what looks to me like an answer to 3 but I am not totally convinced that my proof is really solid. I'm sure that in the late 1990s I heard some version of this problem somewhere, but I don't know where nor exactly which form I saw it in. I think the place I found it only asked for the proof that any four integers eventually reached 0 0 0 0, and that the other parts here are my invention, but I'm not sure of that either. --Joshua Zucker _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun