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

Difference between revisions of "1978 IMO Problems/Problem 3"

(Created page with "yeet")
 
 
Line 1: Line 1:
−
yeet
+
==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 16:01, 29 January 2021

Problem

Let $0<f(1)<f(2)<f(3)<\ldots$ a sequence with all its terms positive$.$ The $n-th$ positive integer which doesn't belong to the sequence is $f(f(n))+1.$ Find $f(240).$

Solution

Since the $n$-th number missing is $f(f(n))+1$ and $f(f(n))$ is a member of the sequence, it results that there are exactly $n-1$ "gaps" less than $f(f(n))$, which leads us to:

$f(f(n))=f(n)+n-1$ $(\star)$

now with a simple induction we can prove that $f(F_{n}+1) = F_{n+1}+f(1)$ , where $F_{k}$ is the Fibonacci sequence.

our next step now is to prove that $f(F_{n}+x) =F_{n+1}+f(x)$, for all $x$ with $1\leq x\leq F_{n-1}$....and agaiiiiin induction(on $n$) : :P

for $n=0$ and $n=1$ it`s trivial and now we supose that it`s true for $n-1$ and to prove that holds for $n$ , in other words $P(n-1) \Rightarrow P(n)$

$(i)$ If $x=f(y)$ for some $y$, then by the inductive assumption and $(\star)$ we have: $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)$


$(ii)$ If $x=f(f(y))+1$ is a gap, then $f(F_{n}+x-1)+1=F_{n+1}+f(x-1)+1$ is a gap also: $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$

It follows that : $f(F_{n}+x)=F_{n+1}+f(x-1)+2=F{n+1}+f(x)$

now since we know that each positive integer $x$ is expressible as: $x=F_{k_{1}}+F_{k_{2}}+...+F_{k_{r}}$ , where $0<k_{r}\neq 2$, $k_{i}\geq k_{i+1}+2$

we obtain that $f(x) = F_{k_{1}+1}+...F_{k_{r}+1}$ and now that we have the general form, pe particulary calculate for $f(240)$:

we can write $240=233+5+2$, therefore $f(240)= 377+8+3=388$

Remark: it can be shown now that $f(x)=[ax]$ , where $a=\frac{1+\sqrt{5}}{2}$

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1978_IMO_Problems/Problem_3&oldid=143966"