n = 2 mod 3 Solution Let f(n) be the number of nice representations of n. We show first that (1) f(2n+1) = f(n), and (2) f(2n) = f(2n-1) + f(n). (1) is almost obvious because n = ∑ a i 2 b i iff 2n+1 = 1 + ∑ a i 2 b i +1 . (2) is also fairly obvious. There are f(n) representations of 2n without a 1 and f(2n-1) with a 1 (because any nice representation of f(2n-1) must have just one 1). We now prove the required result by induction. Let S k be the statement that for n ≤ 6k, f(n) is odd for n = 0, 1 mod 3 and even for n = 2 mod 3. It is easy to check that f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3. So S 1 is true. Suppose S k is true. Then f(6k+1) = f(3k) = odd. f(6k+2) = f(3k+1) + f(6k+1) = odd + odd = even. f(6k+3) = f(3k+1) = odd. f(6k+4) = f(6k+3) + f(3k+2) = odd + even = odd. f(6k+5) = f(3k+2) = odd. So S k+1 is true. So the result is true for all k and hence all n. 2nd OMCC 2000 © John Scholes [email protected] 30 January 2004 Last corrected/updated 30 Jan 04