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

(Solution 2)
m
(28 intermediate revisions by one other user not shown)
Line 19: Line 19:
 
It follows that <math>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}}
 
 
{{IMO box|num-b=5|after=Last question|year=1981}}
 
 
== Solution 2 ==
 
== Solution 2 ==
  
\documentclass{article}
+
We can start by creating a list consisting of certain x an y values and their outputs. <cmath>f(0,0)=1,  f(0,1)=2, f(0,2)=3, f(0,3)=4, f(0,4)=5</cmath>
\usepackage{multirow}
 
\begin{document}
 
\begin{tabular}{ |p{3cm}||p{3cm}|p{3cm}|p{3cm}|  }
 
\hline
 
\multicolumn{4}{|c|}{f(x,y)} \
 
\hline
 
x value & y=0 & y=1 & y=2 \
 
  \hline
 
    & AF    &AFG&  004\
 
Aland Islands&  AX  & ALA  &248\
 
Albania &AL & ALB&  008\
 
Algeria    &DZ & DZA&  012\
 
American Samoa&  AS  & ASM&016\
 
Andorra& AD  & AND  &020\
 
Angola& AO  & AGO&024\
 
\hline
 
\end{tabular}
 
\end{document}
 
  
 +
This pattern can be proved using induction. After proving, we continue to setting a list when <math>x=2</math>. <cmath>f(1,0)=2,  f(1,1)=3,  f(1,2)=4, f(1,3)=5, f(1,4)=6</cmath> This pattern can also be proved using induction. The pattern seems d up of a common difference of 1. Moving on to <math>x=3</math> <cmath>f(3,0)=5,  f(3,1)=13,  f(3,2)=29, f(3,3)=61, f(3,4)=125</cmath> All of the numbers are being expressed in the form of <math>3^a -3
 +
</math> where <math>a=y+3</math>. Lastly where x=4 we have <cmath>f(4,0)=13,  f(4,1)=65533,  f(4,2)=^5 2, f(3,3)=^6 2, f(4,4)=^7 2</cmath> where each term can be represented as <math>^a 2</math> when <math>a=y+2</math>. In <math>^a 2</math> represents tetration or 2 to the power 2 to the power 2 to the power 2 ... where <math>a</math> amount of 2s. So therefore the answer is <math>f(4,1981) = 2^{2\cdot ^{ . \cdot 2}} - 3 </math> with 1984 2s, 2  tetration 1983.
 +
-Multpi12
  
 +
{{alternate solutions}}
  
 
+
{{IMO box|num-b=5|after=Last question|year=1981}}
[[Category:Olympiad Algebra Problems]]
 
[[Category:Functional Equation Problems]]
 

Revision as of 17:15, 12 April 2024

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