IMO 1981 · Problem 6

The function \(f(x,y)\) satisfies \[ \begin{aligned} (1)\quad &f(0,y)=y+1,\\ (2)\quad &f(x+1,0)=f(x,1),\\ (3)\quad &f(x+1,y+1)=f(x,f(x+1,y)), \end{aligned} \] for all non-negative integers \(x,y\). Determine \(f(4,1981)\).

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{f(4,1981)=T_{1984}-3}, \] where \(T_0=1\) and \(T_{n+1}=2^{T_n}\). Thus the answer is a power tower of \(1984\) twos, minus \(3\).

Solution

We determine \(f(x,y)\) successively for \(x=1,2,3,4\).

For \(x=1\), conditions (1) and (2) give \[ f(1,0)=f(0,1)=2. \] Condition (3) gives \[ f(1,y+1)=f(0,f(1,y))=f(1,y)+1. \] Consequently, induction on \(y\) yields \[ f(1,y)=y+2\qquad(y\geq0). \]

For \(x=2\), we similarly obtain \[ f(2,0)=f(1,1)=3, \qquad f(2,y+1)=f(1,f(2,y))=f(2,y)+2. \] Induction therefore gives \[ f(2,y)=2y+3\qquad(y\geq0). \]

For \(x=3\), the initial value and recurrence are \[ f(3,0)=f(2,1)=5, \qquad f(3,y+1)=f(2,f(3,y))=2f(3,y)+3. \] Thus \[ f(3,y+1)+3=2\bigl(f(3,y)+3\bigr). \] Starting from \(f(3,0)+3=8\), induction gives \[ f(3,y)+3=8\cdot2^y, \] so \[ f(3,y)=2^{y+3}-3\qquad(y\geq0). \]

Finally, \[ f(4,0)=f(3,1)=13 \] and \[ f(4,y+1)=f(3,f(4,y)) =2^{f(4,y)+3}-3. \] Put \(g_y=f(4,y)+3\). Then \[ g_0=16,\qquad g_{y+1}=2^{g_y}. \] For the sequence in the answer, \[ T_1=2,\qquad T_2=4,\qquad T_3=16. \] Hence \(g_0=T_3\). If \(g_y=T_{y+3}\), then \[ g_{y+1}=2^{T_{y+3}}=T_{y+4}. \] Induction proves \(g_y=T_{y+3}\) for every non-negative integer \(y\). Taking \(y=1981\), we conclude \[ \boxed{f(4,1981)=T_{1984}-3}. \]

The solution was checked against John Scholes' IMO solution archive (Kalva).