1981 IMO Problems/Problem 6

Problem

The function $f(x,y)$ satisfies

(1) $f(0,y)=y+1,$

(2) $f(x+1,0)=f(x,1),$

(3) $f(x+1,y+1)=f(x,f(x+1,y)),$

for all non-negative integers $x,y$ . Determine $f(4,1981)$ .

Solution

We observe that $f(1,0) = f(0,1) = 2$ and that $f(1, y+1) = f(0, f(1,y)) = f(1,y) + 1$ , so by induction, $f(1,y) = y+2$ . Similarly, $f(2,0) = f(1,1) = 3$ and $f(2, y+1) = f(2,y) + 2$ , yielding $f(2,y) = 2y + 3$ .

We continue with $f(3,0) + 3 = 8$ ; $f(3, y+1) + 3 = 2(f(3,y) + 3)$ ; $f(3,y) + 3 = 2^{y+3}$ ; and $f(4,0) + 3 = 2^{2^2}$ ; $f(4,y) + 3 = 2^{f(4,y-1) + 3}$ .

It follows that $f(4,1981) = 2^{2\cdot ^{ . \cdot 2}} - 3$ when there are 1984 2s, Q.E.D.

Solution 2

We can start by creating a list consisting of certain x an y values and their outputs. $f(0,0)=1, f(0,1)=2, f(0,2)=3, f(0,3)=4, f(0,4)=5$

This pattern can be proved using induction. After proving, we continue to setting a list when $x=2$ . $f(1,0)=2, f(1,1)=3, f(1,2)=4, f(1,3)=5, f(1,4)=6$ This pattern can also be proved using induction. The pattern seems d up of a common difference of 1. Moving on to $x=3$ $f(3,0)=5, f(3,1)=13, f(3,2)=29, f(3,3)=61, f(3,4)=125$ All of the numbers are being expressed in the form of $3^a -3$ where $a=y+3$ . Lastly where x=4 we have $f(4,0)=13, f(4,1)=65533, f(4,2)=^5 2, f(3,3)=^6 2, f(4,4)=^7 2$ where each term can be represented as $^a 2$ when $a=y+2$ . In $^a 2$ represents tetration or 2 to the power 2 to the power 2 to the power 2 ... where $a$ amount of 2s. So therefore the answer is $f(4,1981) = 2^{2\cdot ^{ . \cdot 2}} - 3$ with 1984 2s, 2 tetration 1983. -Multpi12

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1981 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last question
All IMO Problems and Solutions

Page

Toolbox

Search

1981 IMO Problems/Problem 6

Problem

Solution

Solution 2