Difference between revisions of "1981 IMO Problems/Problem 6"
m |
Idk12345678 (talk | contribs) m |
||
(34 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | The function <math> | + | The function <math>f(x,y)</math> satisfies |
− | (1) <math> | + | (1) <math>f(0,y)=y+1, </math> |
− | (2) <math> | + | (2) <math>f(x+1,0)=f(x,1), </math> |
− | (3) <math> | + | (3) <math>f(x+1,y+1)=f(x,f(x+1,y)), </math> |
− | for all non-negative integers <math> | + | for all non-negative integers <math>x,y </math>. Determine <math>f(4,1981) </math>. |
== Solution == | == Solution == | ||
− | We observe that <math> | + | We observe that <math>f(1,0) = f(0,1) = 2 </math> and that <math>f(1, y+1) = f(0, 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> | + | 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> | + | It follows that <math>f(4,1981) = 2^{2\cdot ^{ . \cdot 2}} - 3 </math> 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. <cmath>f(0,0)=1, f(0,1)=2, f(0,2)=3, f(0,3)=4, f(0,4)=5</cmath> |
− | + | 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}} |
Revision as of 17:15, 12 April 2024
Problem
The function satisfies
(1)
(2)
(3)
for all non-negative integers . Determine .
Solution
We observe that and that , so by induction, . Similarly, and , yielding .
We continue with ; ; ; and ; .
It follows that 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.
This pattern can be proved using induction. After proving, we continue to setting a list when . This pattern can also be proved using induction. The pattern seems d up of a common difference of 1. Moving on to All of the numbers are being expressed in the form of where . Lastly where x=4 we have where each term can be represented as when . In represents tetration or 2 to the power 2 to the power 2 to the power 2 ... where amount of 2s. So therefore the answer is 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 |