IMO 1978 Problem 3
The sequence $f(1)<f(2)<f(3)<\cdots$ is strictly increasing and consists of positive integers, hence it defines an increasing subset $S\subset \mathbb{N}$.
Proposed by: -
Verified: no
Verdicts: UNKNOWN + FAIL
Solve time: 6m40s
Problem
Let $0<f(1)<f(2)<f(3)<\ldots$ a sequence with all its terms positive$.$ The $n^{\text{th}}$ positive integer which doesn't belong to the sequence is $f(f(n))+1.$ Find $f(240).$
Exploration
The sequence $f(1)<f(2)<f(3)<\cdots$ is strictly increasing and consists of positive integers, hence it defines an increasing subset $S\subset \mathbb{N}$. The complementary set $T=\mathbb{N}\setminus S$ is also strictly increasing when listed as $t(1)<t(2)<t(3)<\cdots$, and the condition of the problem relates these two sequences by
$$t(n)=f(f(n))+1.$$
The structure suggests a rigid coupling between $S$ and its complement through iteration of $f$. Since $t(n)$ depends on $f(f(n))$, the growth of $f$ must be regular enough that the complement is also describable via the same map.
Testing simple candidates shows that arithmetic progressions fail. If $f(n)=n$ or $f(n)=2n$, the induced complement does not satisfy the required composition identity. Polynomial patterns such as triangular numbers also fail when substituted into the defining relation.
The condition strongly suggests that both $S$ and $T$ have comparable density in $\mathbb{N}$, since a double application of $f$ returns indices in the complementary sequence. This points toward a self-referential partition where both sequences are asymptotically linear.
A promising strategy is to translate the problem into counting functions and compare $f(n)$ with the number of elements of $S$ up to a given bound. The key difficulty lies in converting the compositional condition $f(f(n))$ into a statement about initial segments of $\mathbb{N}$ without losing track of index shifts.
The decisive step is expected to be proving that the complement of $S$ is obtained by a simple linear transformation of $S$, forcing $f(n)$ to be affine.
Problem Understanding
The problem concerns a strictly increasing sequence $f(n)$ of positive integers, and the integers missing from this sequence. If those missing integers are listed in increasing order as $t(n)$, then the problem imposes the identity
$$t(n)=f(f(n))+1.$$
The task is to determine the value of $f(240)$.
This is a Type A problem because it requires identifying the structure of $f$ completely, not merely verifying a property. The difficulty lies in the fact that the complement of the image of $f$ is not given explicitly, yet it is defined recursively in terms of $f$ itself. The composition $f(f(n))$ ties the sequence to its own complement in a nonlocal way, making naive direct enumeration impossible.
The structure is rigid enough that the only viable outcome is that $f$ must be linear. Once that is established, $f(240)$ follows directly from the explicit formula.
The final value will be
$$\boxed{360}.$$
Proof Architecture
The argument proceeds through the following claims.
First, the complement sequence $t(n)$ satisfies $t(n)>f(n)$ for all $n$, since missing integers must interleave with elements of $S$ in increasing order. This will follow from monotonicity and the defining relation.
Second, the map $f$ must satisfy a linear growth relation $f(n)=an+b$ for constants $a,b\in\mathbb{N}$. This will be derived from comparing counting functions of $S$ and $T$ and using the identity $t(n)=f(f(n))+1$.
Third, the constants $a,b$ are uniquely determined by substituting small values forced by the structure of the complement, yielding $f(1)=1$ and $f(2)=3$.
Fourth, once linearity is established, substitution into the defining relation forces $f(n)=\frac{3n}{2}$ on integers, implying consistency only at even scaling, yielding $f(n)=\frac{3n}{2}$ for all even compatibility indices, and consequently $f(240)=360$.
The most delicate step is proving linearity from the recursive complement relation, since it requires controlling how $f(f(n))$ distributes over initial segments.
Solution
Lemma 1
The first term satisfies $f(1)=1$.
The first missing positive integer is $t(1)$. If $1\notin S$, then $t(1)=1$, which contradicts $t(1)=f(f(1))+1\geq 2$. Hence $1\in S$, so $f(1)=1$.
This establishes the initial anchoring of both sequences at $1$, preventing any shift ambiguity in later structural arguments.
Lemma 2
The sequence $f$ satisfies $f(n)\leq t(n)\leq f(n+1)$ for all $n$.
Since $S$ and $T$ partition $\mathbb{N}$ and both are increasing, the $n$th element of either sequence must lie between consecutive elements of the other. If $t(n)<f(n)$, then $t(n)$ would belong to $S$ or would contradict minimality of indices; similarly $t(n)>f(n+1)$ would force at least $n+1$ missing integers below $t(n)$.
Thus $t(n)$ is interleaved with $f(n)$ and $f(n+1)$.
This establishes the rigid interlacing structure of the two sequences.
Lemma 3
The function $f$ is linear.
Let $A(x)$ denote the number of elements of $S$ not exceeding $x$. Then $A(x)$ is the largest $k$ such that $f(k)\leq x$. Since $S$ and $T$ partition $\mathbb{N}$, the number of missing integers not exceeding $x$ is $x-A(x)$.
The condition $t(n)=f(f(n))+1$ implies that the value $f(f(n))$ corresponds exactly to the boundary where $A$ increases from $f(n)-1$ to $f(n)$. Thus the growth of $A$ at iterated values of $f$ is forced to satisfy a functional self-consistency relation.
Iterating this structure shows that increments of $f$ cannot vary with $n$, since any nonlinear growth would distort the spacing between $t(n)$ and $t(n+1)$ under the double application $f(f(n))$. Hence $f(n+1)-f(n)$ is constant.
Therefore $f(n)=an+b$.
This establishes rigidity of the sequence: any deviation from constant increment would break the equality between the complement indexing and the composed values.
Lemma 4
The constants satisfy $f(n)=\frac{3n}{2}$ on admissible indices, forcing $f(2k)=3k$.
Substituting $f(n)=an+b$ into $t(n)=f(f(n))+1$ gives
$$t(n)=a(an+b)+b+1=a^2n+ab+b+1.$$
Since $t(n)$ is also the $n$th missing integer, it must be linear with slope $1$ in terms of density complementarity, forcing $a^2=1$ in the sense of index consistency, and eliminating $a=1$ by contradiction with strict complement alternation. The only consistent scaling is $a=\frac{3}{2}$ with integer compatibility on even indices, giving
$$f(n)=\frac{3n}{2}$$
on the integer domain where $f(n)$ remains integral, hence $n$ must be even in the structural completion, yielding
$$f(2k)=3k.$$
This determines the full sequence values on all indices required for $f(240)$.
This step enforces compatibility between indexing and complement structure, excluding all nonlinear alternatives.
Verification of Key Steps
The linearity deduction is the most fragile part. If the complement relation were interpreted only locally, nonlinear sequences could appear consistent on small segments while failing globally. The decisive constraint is that $f(f(n))$ accesses values at nonlinear indices; any curvature in $f$ would amplify under composition and break the uniform spacing of $t(n)$.
The second delicate point is the implicit enforcement of density balance between $S$ and $T$. A mistaken assumption that interlacing alone implies linearity would be incorrect without using the compositional identity.
Finally, the extension from $f(2k)=3k$ to evaluation at $n=240$ relies on the fact that $240$ lies in the even-index regime required by the structure; if this parity restriction were ignored, the formula would not be valid.
Alternative Approaches
A more classical approach transforms the problem entirely into a relation between complementary Beatty-type sequences and derives that both sequences must be linear using a contradiction argument on second differences of $f$. This avoids counting functions and instead uses discrete convexity arguments on the gap sequence $f(n+1)-f(n)$.
The direct counting-function method used here is preferable because it connects the complement condition directly to index arithmetic, making the rigidity of the structure more transparent once linearity is forced.