35th IMO 1994 shortlist Problem N4 Define the sequences a n , b n , c n as follows. a 0 = k, b 0 = 4, c 0 = 1. If a n is even then a n+1 = a n /2, b n+1 = 2b n , c n+1 = c n . If a n is odd, then a n+1 = a n - b n /2 - c n , b n+1 = b n , c n+1 = b n + c n . Find the number of positive integers k < 1995 such that some a n = 0. Solution
: 31. We call (y, z) a vanishing pair iff (1) y, z are positive integers, (2) y is a power of 2 greater than 2, (3) z  0, a n = 0 for some positive integer n. Note that b n is always a power of 2 and is at least 4. (It starts as 4 and at each step either remains unchanged or doubles.) So c n must be 1 mod 4 (it starts as 1 and always increases by multiples of 4). We cannot have both a n-1 and a n odd. For if a n-1 is odd, then a n = a n-1 - b n-1 /2 - c n-1 = odd - even - odd = even. We claim that if a n is even, then b n+1 > c n+1 and if a n is odd, then 2b n+1 > c n+1 . We use induction. If a 0 is odd, then b 1 = 4, c 1 = 5 and 8 > 5. If a 0 is even, then b 1 = 8, c 1 = 1 and 8 > 1. So it is true for n = 0. Suppose it is true for n-1. If a n is even, then b n+1 = 2b n > c n = c n+1 . If a n is odd, then a n-1 is even (shown above), so 2b n+1 = b n + b n > b n + c n = c n+1 . So it is true for n, and hence for all n. So suppose a 0 leads to a n-1 > 0, a n = 0 for some n. We claim that (b n-1 , c n-1 ) is a vanishing pair. If n = 1, then this is trivial, because the term following (3, 4, 1) is (0, 4, 5). So assume n ≥ 2. We have already established conditions (1), (2) and (4) of the definition. a n-1 cannot be even, for then a n = a n-1 /2 > 0. So a n-1 is odd. Hence a n-2 is even. Hence b n-1 > c n-1 , which establishes (3). So (b n-1 , c n-1 ) is a vanishing pair as claimed. Conversely, suppose (y, z) is a vanishing pair. If (y, z) = (4, 1), then the corresponding x 0 is 3, and the term following (3, 4, 1) is (0, 4, 5). So suppose (y, z) is not (4, 1). We show that we can work backwards to get a term (x 0 , 4, 1). We put x = y/2 + z to give the triple (x, y, z). The previous triple must be (2x, y/2, z) = (x', y', z'). Now if y' > z', then the previous triple (x", y", z") must have had x" even, otherwise we would have z' = y" + z" > y" = y'. So we take x" = 2x', y" = y'/2, z" = z'. If y'  y' or if y = y' and z > z'. The two examples in the previous paragraph bracket 1994, so the vanishing pairs that give x 0 ≤ 1994 are: the 1 + 2 + 4 + 8 + 16 = 31 pairs (4, 1), (8, 1), (8, 5), (16, 1), (16, 5), (16, 9), (16, 13), (32, 1), (32, 5), ... , (32, 29), (64, 1), (64, 5), ... , (64, 61). 35th IMO shortlist 1994 © John Scholes jscholes@kalva.demon.co.uk 18 Sep 2002