Difference between revisions of "1978 IMO Problems/Problem 3"
(Created page with "yeet") |
|||
Line 1: | Line 1: | ||
− | + | ==Problem== | |
+ | Let <math>0<f(1)<f(2)<f(3)<\ldots</math> a sequence with all its terms positive<math>.</math> The <math>n-th</math> positive integer which doesn't belong to the sequence is <math>f(f(n))+1.</math> Find <math>f(240).</math> | ||
+ | |||
+ | ==Solution== | ||
+ | Since the <math>n</math>-th number missing is <math>f(f(n))+1</math> and <math>f(f(n))</math> is a member of the sequence, it results that there are exactly <math>n-1</math> "gaps" less than <math>f(f(n))</math>, which leads us to: | ||
+ | |||
+ | <math>f(f(n))=f(n)+n-1</math> <math>(\star)</math> | ||
+ | |||
+ | now with a simple induction we can prove that <math>f(F_{n}+1) = F_{n+1}+f(1)</math> , where <math>F_{k}</math> is the Fibonacci sequence. | ||
+ | |||
+ | our next step now is to prove that <math>f(F_{n}+x) =F_{n+1}+f(x)</math>, for all <math>x</math> with <math>1\leq x\leq F_{n-1}</math>....and agaiiiiin induction(on <math>n</math>) : :P | ||
+ | |||
+ | for <math>n=0</math> and <math>n=1</math> it`s trivial and now we supose that it`s true for <math>n-1</math> and to prove that holds for <math>n</math> , in other words <math>P(n-1) \Rightarrow P(n)</math> | ||
+ | |||
+ | <math>(i)</math> If <math>x=f(y)</math> for some <math>y</math>, then by the inductive assumption and <math>(\star)</math> we have: | ||
+ | <math>f(F_{n}+x)=f(F_{n}+f(y))=f(f(F_{n-1}+y))=F_{n}+f(y)+F_{n-1}+y-1=F_{n+1}+f(x)</math> | ||
+ | |||
+ | |||
+ | <math>(ii)</math> If <math>x=f(f(y))+1</math> is a gap, then <math>f(F_{n}+x-1)+1=F_{n+1}+f(x-1)+1</math> is a gap also: | ||
+ | <math>F_{n+1}+f(x)+1=F_{n+1}+f(f(f(y)))+1=f(F_{n}+f(f(y)))+1=f(f(F_{n-1}+f(y)))+1</math> | ||
+ | |||
+ | It follows that : <math>f(F_{n}+x)=F_{n+1}+f(x-1)+2=F{n+1}+f(x)</math> | ||
+ | |||
+ | now since we know that each positive integer <math>x</math> is expressible as: | ||
+ | <math>x=F_{k_{1}}+F_{k_{2}}+...+F_{k_{r}}</math> , where <math>0<k_{r}\neq 2</math>, <math>k_{i}\geq k_{i+1}+2</math> | ||
+ | |||
+ | we obtain that <math>f(x) = F_{k_{1}+1}+...F_{k_{r}+1}</math> and now that we have the general form, pe particulary calculate for <math>f(240)</math>: | ||
+ | |||
+ | we can write <math>240=233+5+2</math>, therefore <math>f(240)= 377+8+3=388</math> | ||
+ | |||
+ | Remark: it can be shown now that <math>f(x)=[ax]</math> , where <math>a=\frac{1+\sqrt{5}}{2}</math> | ||
+ | |||
+ | The above solution was posted and copyrighted by pohoatza. The original thread for this problem can be found here: [https://aops.com/community/p667873] | ||
+ | |||
+ | == See Also == {{IMO box|year=1978|num-b=2|num-a=4}} |
Latest revision as of 17:01, 29 January 2021
Problem
Let a sequence with all its terms positive The positive integer which doesn't belong to the sequence is Find
Solution
Since the -th number missing is and is a member of the sequence, it results that there are exactly "gaps" less than , which leads us to:
now with a simple induction we can prove that , where is the Fibonacci sequence.
our next step now is to prove that , for all with ....and agaiiiiin induction(on ) : :P
for and it`s trivial and now we supose that it`s true for and to prove that holds for , in other words
If for some , then by the inductive assumption and we have:
If is a gap, then is a gap also:
It follows that :
now since we know that each positive integer is expressible as: , where ,
we obtain that and now that we have the general form, pe particulary calculate for :
we can write , therefore
Remark: it can be shown now that , where
The above solution was posted and copyrighted by pohoatza. The original thread for this problem can be found here: [1]
See Also
1978 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |