IMO 1981 Problem B3 The function f(x,y) satisfies: f(0,y) = y + 1, f(x+1,0) = f(x,1), f(x+1,y+1) = f(x,f(x+1,y)) for all non- negative integers x, y. Find f(4, 1981).
f(1,n) = f(0,f(1,n-1)) = 1 + f(1,n-1). So f(1,n) = n + f(1,0) = n + f(0,1) = n + 2. f(2,n) = f(1,f(2,n-1)) = f(2,n-1) + 2. So f(2,n) = 2n + f(2,0) = 2n + f(1,1) = 2n + 3. f(3,n) = f(2,f(3,n-1)) = 2f(3,n-1) + 3. Let u n = f(3,n) + 3, then u n = 2u n-1 . Also u 0 = f(3,0) + 3 = f(2,1) + 3 = 8. So u n = 2 n+3 , and f(3,n) = 2 n+3 - 3. f(4,n) = f(3,f(4,n-1)) = 2 f(4,n-1)+3 - 3. f(4,0) = f(3,1) = 2 4 - 3 = 13. We calculate two more terms to see the pattern: f(4,1) = 2 2 4 - 3, f(4,2) = 2 2 2 4 - 3. In fact it looks neater if we replace 4 by 2 2 , so that f(4,n) is a tower of n+3 2s less 3. s are also available in Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48- X. 22nd IMO 1981 © John Scholes jscholes@kalva.demon.co.uk 12 Oct 1998