IMO 1981 SL 7

Origin: FIN

Problem

Assume that f(x, y) is defined for all positive integers x and y, and that the following equations are satisfied: f(0, y) = y + 1, f(x + 1, 0) = f(x, 1), f(x + 1, y + 1) = f(x, f(x + 1, y)). Determine f(2, 2), f(3, 3) and f(4, 4). Alternative version: Determine f(4, 1981).

Solution

We immediately find that f(1, 0) = f(0, 1) = 2. Then f(1, y + 1) = f(0, f(1, y)) = f(1, y) + 1; hence f(1, y) = y + 2 for y \geq0. Next we find that f(2, 0) = f(1, 1) = 3 and f(2, y +1) = f(1, f(2, y)) = f(2, y)+2, from which f(2, y) = 2y + 3. Particularly, f(2, 2) = 7. Further, f(3, 0) = f(2, 1) = 5 and f(3, y + 1) = f(2, f(3, y)) = 2f(3, y) + 3. This gives by induction f(3, y) = 2y+3 −3. For y = 3, f(3, 3) = 61. Finally, from f(4, 0) = f(3, 1) = 13 and f(4, y + 1) = f(3, f(4, y)) = 2f(4,y)+3 −3, we conclude that f(4, y) = 22...2 −3 (y + 3 twos).