10th Chinese 1995 Problem A2 N + is the set of positive integers. f: N + → N + satisfies f(1) = 1, f(2n) < 6 f(n), and 3 f(n) f(2n+1) = f(2n) + 3 f(n) f(2n) for all n. Find all m, n such that f(m) + f(n) = 293.
3 f(n) is coprime to 1 + 3 f(n), and divides f(2n) (1 + 3 f(n) ), so it must divide f(2n). But f(2n) < 2·3f(n), so f(2n) = 3 f(n). Hence f(2n+1) = 3 f(n) + 1. So it is almost obvious (and an easy induction to prove) that to get f(n) we write n in binary and treat the result as ternary. For example, f(23) = f(10111 2 ) = 10111 3 = 81 + 9 + 3 + 1 = 94. We have 293 = 101212 3 . If we write this as the sum of two numbers without 2s, then there can be no carries, and both numbers must have 1s where 293 has 2s, so the only possibilities are 101111 + 101, 101101 + 111, 100111 + 1101, 100101 + 1111. So the possible pairs are (47, 5), (45, 7), (39, 13), (37 ,15). 10th Chinese 1995 © John Scholes jscholes@kalva.demon.co.uk 5 Jan 2003