Maths Olympiad Prep

Library / /110 of 520

Number theory Difficulty 5.8 AIME, harder Find the answer

9. (GBR5)IMO3\mathbf{( G B R} \mathbf{5})^{\mathrm{IMO} 3} Let {f(n)}\{f(n)\} be a strictly increasing sequence of positive integers: 0<f(1)<f(2)<f(3)<0<f(1)<f(2)<f(3)<\cdots. Of the positive integers not belonging to the sequence, the nnth in order of magnitude is f(f(n))+1f(f(n))+1. Determine f(240)f(240).

A number or a short expression. Spacing and $ signs are ignored.

Solution

9. Since the nnth missing number (gap) is f(f(n))+1f(f(n))+1 and f(f(n))f(f(n)) is a member of the sequence, there are exactly n1n-1 gaps less than f(f(n))f(f(n)). This leads to
f(f(n))=f(n)+n1 f(f(n))=f(n)+n-1
Since 1 is not a gap, we have f(1)=1f(1)=1. The first gap is f(f(1))+1=2f(f(1))+1=2. Two consecutive integers cannot both be gaps (the predecessor of a gap is of the form f(f(m))f(f(m))). Now we deduce f(2)=3f(2)=3; a repeated application of the formula above gives f(3)=3+1=4,f(4)=4+2=6,f(6)=9f(3)=3+1=4, f(4)=4+2=6, f(6)=9, f(9)=14,f(14)=22,f(22)=35,f(35)=56,f(56)=90,f(90)=145f(9)=14, f(14)=22, f(22)=35, f(35)=56, f(56)=90, f(90)=145, f(145)=234,f(234)=378f(145)=234, f(234)=378. Also, f(f(35))+1=91f(f(35))+1=91 is a gap, so f(57)=92f(57)=92. Then by (1), f(92)=148f(92)=148, f(148)=239,f(239)=386f(148)=239, f(239)=386. Finally, here f(f(148))+1=387f(f(148))+1=387 is a gap, so f(240)=388f(240)=388.

Second solution. As above, we arrive at formula (1). Then by simple induction it follows that f(Fn+1)=Fn+1+1f\left(F_{n}+1\right)=F_{n+1}+1, where FkF_{k} is the Fibonacci sequence ( F1=F2=1F_{1}=F_{2}=1 ). We now prove by induction (on nn) that f(Fn+x)=Fn+1+f(x)f\left(F_{n}+x\right)=F_{n+1}+f(x) for all xx with 1xFn11 \leq x \leq F_{n-1}. This is trivially true for n=0,1n=0,1. Supposing that it holds for n1n-1, we shall prove it for nn:
(i) If x=f(y)x=f(y) for some yy, then by the inductive assumption and (1)
f(Fn+x)=f(Fn+f(y))=f(f(Fn1+y))=Fn+f(y)+Fn1+y1=Fn+1+f(x) \begin{aligned} f\left(F_{n}+x\right) & =f\left(F_{n}+f(y)\right)=f\left(f\left(F_{n-1}+y\right)\right) \\ & =F_{n}+f(y)+F_{n-1}+y-1=F_{n+1}+f(x) \end{aligned}
(ii) If x=f(f(y))+1x=f(f(y))+1 is a gap, then f(Fn+x1)+1=Fn+1+f(x1)+1f\left(F_{n}+x-1\right)+1=F_{n+1}+f(x-1)+1 is a gap also:
Fn+1+f(x)+1=Fn+1+f(f(f(y)))+1=f(Fn+f(f(y)))+1=f(f(Fn1+f(y)))+1 \begin{aligned} F_{n+1}+f(x)+1 & =F_{n+1}+f(f(f(y)))+1 \\ & =f\left(F_{n}+f(f(y))\right)+1=f\left(f\left(F_{n-1}+f(y)\right)\right)+1 \end{aligned}
It follows that f(Fn+x)=Fn+1+f(x1)+2=Fn+1+f(x)f\left(F_{n}+x\right)=F_{n+1}+f(x-1)+2=F_{n+1}+f(x). Now, since we know that each positive integer xx is expressible as x=x= Fk1+Fk2++FkrF_{k_{1}}+F_{k_{2}}+\cdots+F_{k_{r}}, where 0<kr2,kiki+1+20<k_{r} \neq 2, k_{i} \geq k_{i+1}+2, we obtain f(x)=Fk1+1+Fk2+1++Fkr+1f(x)=F_{k_{1}+1}+F_{k_{2}+1}+\cdots+F_{k_{r}+1}. Particularly, 240=233+5+2240=233+5+2, so f(240)=377+8+3=388f(240)=377+8+3=388. Remark. It can be shown that f(x)=[αx]f(x)=[\alpha x], where α=(1+5)/2\alpha=(1+\sqrt{5}) / 2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.