Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1981 IMO Problems/Problem 6: Difference between revisions

← Older editNewer edit →
mNo edit summary
m →Solution: matho
Line 17: Line 17:
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>\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>.


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


{{alternate solutions}}
{{alternate solutions}}

Revision as of 16:39, 29 October 2006

Problem

The function $\displaystyle f(x,y)$ satisfies

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

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

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

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

Solution

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

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

It follows that $\displaystyle 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.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1981_IMO_Problems/Problem_6&oldid=10505"