From: bruck@math.usc.edu (Ronald Bruck) Newsgroups: sci.math,rec.puzzles Subject: Re: Russian 44 puzzle Date: 30 Sep 1998 22:41:11 -0700 In article <6utulj$ke4$1@news1.rmi.net>, Kurt Foster wrote: >In sci.math John Scholes wrote: >. Given n odd and a set of integers a_1, a_2, ... , a_n, derive a new set >. (a_1+a_2)/2, (a_2+a_3)/2, ... , (a_(n-1)+a_n)/2, (a_n+a_1)/2. However >. many times we repeat this process for a particular starting set we >. always get integers. Prove that all the numbers in the starting set are >. equal. [SPOILER after about 30 lines] [solution omitted] I'm not going to give the "spoiler" lineage, because my solution is more than 30 lines away!! Of course, it's not the simplest, but: This problem has interesting generalizations and interpretations. The matrix which maps (a1,...,aN) to ((a1+a2)/2, (a2+a3)/2, ..., (aN+a1)/2) is called a "circulant", as I recall. When you apply it to points ai in the plane, after a finite number of iterations the path joining each coordinate to the next forms a convex polygon. It's amusing to program this and watch it. The original points may have a VERY complicated and self-intersecting path a1 -> a2 -> a3 ... -> aN ->a1, but as you iterate, it slowly unravels itself until it's convex. Now the transformation reduces the area of the polygon in the plane, but leaves the center of mass fixed. Thus unless you want to see the iterates quickly shrink to a point, you'd better rescale the polygon (relative to its COM) to have area 1 (although these are signed areas, and the apparent size may grow as the curve unravels itself--and switches negative areas to positive areas). You might expect that this normalized figure will converge, but it doesn't; for example, start with a square: alternately you get the square and the diamond (after normalizing the areas). To understand the convergence another way, let S be the mapping which does a "rotate left": (x1,...,xn) -> (x2,x3,...,xn,x1). The desired transformation T is (I+S)/2 (which is to be iterated on the original vertices). Now S is an isometry, so ||S|| = 1 in the Euclidean norm. I claim that ||T^(n+1) - T^n|| <= cst/sqrt{n}. The sharpest way to see this is to expand both (I+S)^(n+1) and (I+S)^n by the binomial theorem, obtaining T^(n+1) - T^n = \sum_p (C(n+1,p)/2^(n+1) - C(n,p)/2^n) S^p = \sum_p (C(n,p) + C(n,p-1) - 2C(n,p)) S^p/2^(n+1) so that ||T^(n+1) - T^n|| <= \sum_p |C(n,p) - C(n,p-1)| / 2^(n+1). But the binomial coefficients increase from p = 0 up to p = n/2; so the first part of the sum telescopes to C(n,n/2)/2^(n+1). And the second part also telescopes, also to C(n,n/2)/2^(n+1). (When n is odd, you can take the floor or ceiling of n/2, it doesn't matter.) Thus ||T^(n+1) - T^n|| <= C(n,n/2)/2^n. The estimate that this is (mumble) I think it's < sqrt{2/(pi n)) is a standard exercise in approximating factorials. HOWEVER, the convergence of ||T^(n+1) - T^n|| to zero does NOT, by itself, prove that {T^nx} converges. Fortunately, for this kind of T it DOES: for T acts in a compact set (the closed unit ball of R^N), so that {T^nx} has a convergent subsequence. If z is a subsequential limit, say T^n(i)x --> z, then we simultaneously have T^(n(i)+1)x --> Tz (by applying T to both sides), and T^n(i)x --> z (since T^(n+1)-T^n --> 0) and thus z = Tz. But hold on: if Tz = z, then the sequence {||T^nx - z||} must be decreasing: for since ||T|| <= 1 we have ||T^(n+1)x - z|| = ||T^(n+1)x - Tz|| <= ||T^nx - z||. But if {||T^nx - z||} is decreasing and a subsequence goes to zero, then the WHOLE sequence goes to zero; i.e. T^n x converges to a fixed-point of T. A fixed point of T := (I+S)/2 is obviously a fixed-point of S, and the only fixed-points of S are vectors of the form (x1,x2,...,xN) where x1 = x2 = ... = xN. There's another way to see the convergence of T^(n+1) - T^n; it's to prove the UNIFORM convergence of ((1+z)/2)^(n+1) - ((1+z)/2)^n to zero for complex |z| <= 1. That's curious in itself, because ((1+z)/2)^n DOESN'T converge uniformly (problem near z = 1). Anyway, when you apply the maximum modulus principle to ((1+z)/2)^(n+1) - ((1+z)/2)^n you get another proof of the uniform convergence (which is then extended to the operator T by the usual functional-calculus considerations). Indeed, in ANY Banach space, if S is a NONLINEAR mapping of a bounded closed convex set C back into itself, and S has Lipschitz constant 1, it follows (for T = (I+S)/2) that diam C ||T^(n+1)x - T^nx|| <= ----------- sqrt(pi * n) This result was proved by Jean-Bernard Baillon and myself around 1995, and can be found in the volume 178 of Lecture Notes in Pure and Applied Mathematics, Marcel Dekker. The proof for the nonlinear case is VERY difficult. In the finite-dimensional linear case, the one needed by this problem, the convergence of T^nx is of course exponential. To see this, mod-out by the kernel of I-T, and note that the induced map T0 satisfies T0^n --> 0. (There IS an induced map because Ker(I-T) = Ker(I-T*).) Thus all the eigenvalues of T0 are < 1 in absolute value, and hence its spectral radius is < 1 (= max of abs values of eigenvalues, since this is a finite-dimensional space). Thus in fact T0^n --> 0 like k^n, where k is the absolute value of the largest eigenvalue; from which it follows that also T^nx --> z linearly. In the infinite-dimensional case, even the LINEAR infinite-dimensional case, the cst/sqrt(n) is sharp. (Look at the right-hand shift in little-ell- infinity.) And I suppose that if you join INFINITELY many points in the plane together (whatever that means), it takes infinitely long for the polygonal line to straighten itself out into a convex set. --Ron Bruck From: bruck@math.usc.edu (Ronald Bruck) Newsgroups: sci.math,rec.puzzles Subject: Re: Russian 44 puzzle Date: 1 Oct 1998 00:15:32 -0700 In article <6uv4ln$pgp$1@math.usc.edu>, Ronald Bruck wrote: : :There's another way to see the convergence of T^(n+1) - T^n; it's to prove :the UNIFORM convergence of ((1+z)/2)^(n+1) - ((1+z)/2)^n to zero for complex :|z| <= 1. That's curious in itself, because ((1+z)/2)^n DOESN'T :converge uniformly (problem near z = 1). Anyway, when you apply the maximum :modulus principle to ((1+z)/2)^(n+1) - ((1+z)/2)^n you get another proof of :the uniform convergence (which is then extended to the operator T by the :usual functional-calculus considerations). When I posted this, I couldn't remember the details of the proof. It's funny that ((1+z)/2)^n doesn't converge uniformly, but the difference does; is there a general result which would yield this? Anyway, simplify fn(z) = ((1+z)/2)^(n+1) - ((1+z)/2)^n to fn(z) = ((1+z)/2)^n * (z-1)/2. Since this is analytic on |z| <=1 (it's a polynomial!), the maximum value on |z| <= 1 is taken on |z| = 1. Thus we can set z = exp(i t), and |fn(z)| = |(1+exp(it))|^n |(exp(i t)-1)/2| = cos^n (t/2) |sin(t/2)|. To maximize this, we set the derivative equal to zero; this can't happen where sin(t/2) = 0, so WLOG we can take our function to be cos^n(t/2) sin(t/2). Setting the derivative equal to zero and solving, we get (if I'm not mistaken) cos^2 (t/2) = n sin^2 (t/2), thus cos^2 (t/2) = n/(n+1), sin^2(t/2) = 1/(n+1); hence the max is |fn|_max = [n/(n+1)]^(n/2) /sqrt(n+1). And the [n/(n+1)]^(n/2) converges to exp(-1/2), thus our estimate is something like 1 |f_n(z)| < --------- sqrt(e*n) This is a shade better than the sqrt(2/(pi*n)) that we get in the infinite- dimensional case. --Ron Bruck