Difference between revisions of "1981 IMO Problems/Problem 6"

m (Solution: matho)
m
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
The function <math>\displaystyle f(x,y)</math> satisfies
+
The function <math>f(x,y)</math> satisfies
  
(1) <math> \displaystyle f(0,y)=y+1, </math>
+
(1) <math>f(0,y)=y+1, </math>
  
(2) <math> \displaystyle f(x+1,0)=f(x,1), </math>
+
(2) <math>f(x+1,0)=f(x,1), </math>
  
(3) <math> \displaystyle f(x+1,y+1)=f(x,f(x+1,y)), </math>
+
(3) <math>f(x+1,y+1)=f(x,f(x+1,y)), </math>
  
for all non-negative integers <math> \displaystyle x,y </math>. Determine <math> \displaystyle f(4,1981) </math>.
+
for all non-negative integers <math>x,y </math>. Determine <math>f(4,1981) </math>.
  
 
== Solution ==
 
== Solution ==
  
We observe that <math>\displaystyle f(1,0) = f(0,1) = 2 </math> and that <math>\displaystyle f(1, y+1) = f(1, f(1,y)) = f(1,y) + 1</math>, so by induction, <math>\displaystyle f(1,y) = y+2 </math>.  Similarly, <math>\displaystyle f(2,0) = f(1,1) = 3</math> and <math>\displaystyle f(2, y+1) = f(2,y) + 2</math>, yielding <math>\displaystyle f(2,y) = 2y + 3</math>.
+
We observe that <math>f(1,0) = f(0,1) = 2 </math> and that <math>f(1, y+1) = f(1, f(1,y)) = f(1,y) + 1</math>, so by induction, <math>f(1,y) = y+2 </math>.  Similarly, <math>f(2,0) = f(1,1) = 3</math> and <math>f(2, y+1) = f(2,y) + 2</math>, yielding <math>f(2,y) = 2y + 3</math>.
  
We continue with <math>\displaystyle f(3,0) + 3 = 8 </math>; <math>\displaystyle f(3, y+1) + 3 = 2(f(3,y) + 3)</math>; <math>\displaystyle f(3,y) + 3 = 2^{y+3}</math>; and <math>\displaystyle f(4,0) + 3 = 2^{2^2}</math>; <math>\displaystyle f(4,y) + 3 = 2^{f(4,y) + 3}</math>.
+
We continue with <math>f(3,0) + 3 = 8 </math>; <math>f(3, y+1) + 3 = 2(f(3,y) + 3)</math>; <math>f(3,y) + 3 = 2^{y+3}</math>; and <math>f(4,0) + 3 = 2^{2^2}</math>; <math>f(4,y) + 3 = 2^{f(4,y) + 3}</math>.
  
It follows that <math>\displaystyle f(4,1981) = 2^{2\cdot ^{ . \cdot 2}} - 3 </math> when there are 1984 2s, Q.E.D.
+
It follows that <math>f(4,1981) = 2^{2\cdot ^{ . \cdot 2}} - 3 </math> when there are 1984 2s, Q.E.D.
  
 
{{alternate solutions}}
 
{{alternate solutions}}
  
== Resources ==
+
{{IMO box|num-b=5|after=Last question|year=1981}}
 
 
* [[1981 IMO Problems]]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366648#p366648 AoPS/MathLinks Discussion]
 
 
 
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]
 +
[[Category:Functional Equation Problems]]

Revision as of 08:40, 19 July 2016

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(1, 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) + 3}$.

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

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