IMO 1981/B3 solution

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).

Solution

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₀ = f(3,0) + 3 = f(2,1) + 3 = 8. So u_n = 2ⁿ⁺³, and f(3,n) = 2ⁿ⁺³ - 3.

f(4,n) = f(3,f(4,n-1)) = 2^f(4,n-1)+3 - 3. f(4,0) = f(3,1) = 2⁴ - 3 = 13. We calculate two more terms to see the pattern: f(4,1) = 2^2⁴ - 3, f(4,2) = 2^{2^2⁴} - 3. In fact it looks neater if we replace 4 by 2², so that f(4,n) is a tower of n+3 2s less 3.

Solutions 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