Number theoryDifficulty 5.8AIME, harderFind the answer
9. (GBR5)IMO3 Let {f(n)} be a strictly increasing sequence of positive integers: 0<f(1)<f(2)<f(3)<⋯. Of the positive integers not belonging to the sequence, the nth in order of magnitude is f(f(n))+1. Determine f(240).
A number or a short expression. Spacing and $ signs are ignored.
Solution
9. Since the nth missing number (gap) is f(f(n))+1 and f(f(n)) is a member of the sequence, there are exactly n−1 gaps less than f(f(n)). This leads to f(f(n))=f(n)+n−1 Since 1 is not a gap, we have f(1)=1. The first gap is f(f(1))+1=2. Two consecutive integers cannot both be gaps (the predecessor of a gap is of the form f(f(m))). Now we deduce f(2)=3; a repeated application of the formula above gives f(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)=145, f(145)=234,f(234)=378. Also, f(f(35))+1=91 is a gap, so f(57)=92. Then by (1), f(92)=148, f(148)=239,f(239)=386. Finally, here f(f(148))+1=387 is a gap, so f(240)=388.
Second solution. As above, we arrive at formula (1). Then by simple induction it follows that f(Fn+1)=Fn+1+1, where Fk is the Fibonacci sequence ( F1=F2=1 ). We now prove by induction (on n) that f(Fn+x)=Fn+1+f(x) for all x with 1≤x≤Fn−1. This is trivially true for n=0,1. Supposing that it holds for n−1, we shall prove it for n: (i) If x=f(y) for some y, then by the inductive assumption and (1) f(Fn+x)=f(Fn+f(y))=f(f(Fn−1+y))=Fn+f(y)+Fn−1+y−1=Fn+1+f(x) (ii) If x=f(f(y))+1 is a gap, then f(Fn+x−1)+1=Fn+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(Fn−1+f(y)))+1 It follows that f(Fn+x)=Fn+1+f(x−1)+2=Fn+1+f(x). Now, since we know that each positive integer x is expressible as x=Fk1+Fk2+⋯+Fkr, where 0<kr=2,ki≥ki+1+2, we obtain f(x)=Fk1+1+Fk2+1+⋯+Fkr+1. Particularly, 240=233+5+2, so f(240)=377+8+3=388. Remark. It can be shown that f(x)=[αx], where α=(1+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.