Diminishing Differences Puzzle
Source: Australian Mathematical Society Gazette Puzzle Corner 34 Problem: Begin with n integers x1, . . . , xn around a circle. At each turn, simultaneously replace all of them by the absolute differences Repeat this process until every number is 0, then stop. Prove that this process always terminates if and only if n is a power of 2. Shameless plug: Follow CSE Blog on CSE Blog - Twitter and CSE Blog on Quora . :-) Solution: Highlight the part between the * symbols for the answer. * These are Ducci sequences; the answer is driven by arithmetic mod 2. Step 1 (mod 2): over GF(2), absolute difference is just addition: x_i -> x_i + x_(i+1). After k steps the entries are given by binomial coefficients of (1+z)^k around the cycle. If n = 2^m, then (1+z)^n = 1 + z^n (mod 2), and around a cycle of length n, z^n = 1 - so after n steps every entry becomes x_i + x_i = 0: all even numbers. If n is not a power of 2, write n = 2^m * k with k odd > 1: the 3-cycle (0,1...