IMO 1978 · Problem 3

The set of all positive integers is the union of two disjoint subsets \(\{f(1),f(2),\ldots,f(n),\ldots\}\), \(\{g(1),g(2),\ldots,g(n),\ldots\}\) where \[ f(1)<f(2)<\cdots<f(n)<\cdots, \] \[ g(1)<g(2)<\cdots<g(n)<\cdots, \] and \[ g(n)=f(f(n))+1\text{ for all }n\geq1. \] Determine \(f(240)\).

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{f(240)=388}. \]

Solution

First, count the positive integers strictly less than \(g(n)\). Since \[ g(n)-1=f(f(n)), \] exactly \(f(n)\) of them belong to the \(f\)-sequence, and exactly \(n-1\) belong to the \(g\)-sequence. The two sequences partition the positive integers, so \[ g(n)-1=f(n)+n-1, \] and therefore \[ \boxed{g(n)=f(n)+n}. \]

There is at most one pair of strictly increasing complementary sequences satisfying this last identity. Indeed, for every \(n\), \(f(n)\) must be the smallest positive integer absent from \[ \{f(i),g(i):1\leq i<n\}. \] To see this, \(f(n)\) itself is absent by strict increase and disjointness. Every smaller positive integer is either an earlier \(f\)-term or a \(g\)-term; and it must be an earlier \(g\)-term because \[ g(i)=f(i)+i>f(n)\qquad(i\geq n). \] Thus the displayed rule determines \(f(n)\) from the earlier pairs, after which \(g(n)=f(n)+n\) determines \(g(n)\). Starting with \(f(1)=1\), uniqueness follows by induction.

We now construct this pair. Put \[ \alpha=\frac{1+\sqrt5}{2},\qquad F(n)=\lfloor n\alpha\rfloor,\qquad G(n)=\lfloor n\alpha^2\rfloor. \] Since \(\alpha^2=\alpha+1\), we have \[ G(n)=F(n)+n. \] Both sequences are strictly increasing, because \(\alpha>1\) and \(\alpha^2>1\).

It remains to prove that their ranges partition the positive integers. For any integer \(m\geq0\), the number of terms of \(F\) not exceeding \(m\) is \[ \#\{n\geq1:\lfloor n\alpha\rfloor\leq m\} =\left\lfloor\frac{m+1}{\alpha}\right\rfloor, \] since the condition is equivalent to \(n<(m+1)/\alpha\), whose right-hand side is irrational. Similarly, the corresponding number for \(G\) is \[ \left\lfloor\frac{m+1}{\alpha^2}\right\rfloor. \] But \[ \frac1\alpha+\frac1{\alpha^2}=1. \] Consequently, the two irrational numbers inside these floors sum to the integer \(m+1\), so their floors sum to \(m\). Hence there are exactly \(m\) occurrences, counted across both sequences, of integers at most \(m\).

For each \(m\geq1\), subtracting the total count at \(m-1\) from that at \(m\) shows that \(m\) occurs exactly once. Thus \(F\) and \(G\) are complementary. By the uniqueness proved above, \[ f(n)=\left\lfloor\frac{n(1+\sqrt5)}2\right\rfloor. \]

Finally, \[ 240\alpha=120+120\sqrt5. \] Since \[ 268^2=71824<72000=(120\sqrt5)^2<72361=269^2, \] we obtain \(388<240\alpha<389\). Therefore \[ \boxed{f(240)=388}. \]

The solution was checked against John Scholes' IMO solution archive (Kalva).