1978 IMO Problems/Problem 3

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]

1978 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search

1978 IMO Problems/Problem 3

Problem

Solution

See Also