25th ASU 1991 Problem 11 The numbers 1, 2, 3, ... , n are written on a blackboard (where n ≥ 3). A move is to replace two numbers by their sum and non-negative difference. A series of moves makes all the numbers equal k. Find all possible k.
all powers of 2 ≥ n Solution If a prime p divides a+b and a-b, then it divides 2a and 2b, so if p is odd, it divides a and b. Thus if an odd prime p divides k, then it must divide all the original numbers including 1. So k must be a power of 2. Note that k, k → 0, 2k → 2k, 2k and k, k, k → 0, k, 2k → k, k, 2k → 0, 2k, 2k → 2k, 2k, 2k. So (by a trivial induction) if we get all the numbers equal to k, then we can get them all to equal 2k. Finally, note that we can never decrease the largest number on the board, so the answer must be all powers of 2 greater than some minimum, which must be at least n. We use induction to show that if 2 m is the smallest power of 2 which is ≥ n, then we can get all numbers equal to 2 m . Note that 0, k → k, k → 0, 2k, so with a zero we can double each member of any set of numbers as often as we wish and finally convert the zero. For example, we could convert 0, 2, 4 to 8, 8, 8. It is convenient to take the induction hypothesis as S n : we can convert 1, 2, ... , n to 0, 2 k , 2 k , ... , 2 k , where 2 k is the smallest power of 2 which is ≥ n. We show first that S n is true for n ≤ 8. For n = 3, we take 1,3 → 2,4, then 2,2 → 0,4. For n = 4, we ignore the 4 and use the case n = 3. For n = 5, we take 3,5 → 2,8. Then 2,2 → 0,4. Then we use the 0 to convert the remaining powers of 2 (1,4,4) to 8. For n = 6, we take 2,6 → 4,8 and 3,5 → 2,8, then 4,4 → 0,8. Finally, we use the 0 to convert 1 and 2 to 8. For n = 7, we take 1,7 → 6,8, then 2,6 → 4,8, then 3,5 → 2,8, then 4,4 → 0,8, then 2,6 → 4,8 and finally use the 0 to convert the remaining 4 to 8. Let n = 2 a + b, where 0  2, so by induction we can convert 1, 2, ... , 2 a -2 to 0, 2 a , ... , 2 a . Now all the numbers except 0 are powers of 2 and we can use the 0 to convert them each to 2 a+1 . Similarly, if b = 2, we convert 2 a -1, 2 a +1 to 2, 2 a+1 and 2 a -2, 2 a +2 to 4, 2 a+1 and then proceed as in the previous case. If 3 ≤ b < 2 a , then we start by converting the pairs (2 a + b, 2 a - b), (2 a + b-1, 2 a - b+1), (2 a + b-2, 2 a - b+2), ... , (2 a + 1, 2 a - 1). That gives some 2 a+1 s and 2, 4, ... , 2b. Now by S b we can convert 2, 4, ... , 2b to 0, 2 a+1 , ... , 2 a+1 . The remaining numbers 1, 2, ... , 2 a -b-1 can either be converted to powers of 2 by S 2 a -b-1 (if 2 a -b-1 ≥ 3) or are already powers of 2. Finally we use the 0 to bring all powers of 2 up to 2 a+1 . In the case b = 2 a , we ignore 2 a + b (= 2 a+1 ) and use the case b-1 to convert the others. 25th ASU 1991 © John Scholes jscholes@kalva.demon.co.uk 14 March 2004 Last corrected/updated 14 Mar 04