IMO 1988 Problem 3
Testing the recursion directly shows that fixed points are sparse but structured.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 14m49s
Problem
A function $f$ defined on the positive integers (and taking positive integers values) is given by:
$\begin{matrix} f(1) = 1, f(3) = 3 \ f(2 \cdot n) = f(n) \ f(4 \cdot n + 1) = 2 \cdot f(2 \cdot n + 1) - f(n) \ f(4 \cdot n + 3) = 3 \cdot f(2 \cdot n + 1) - 2 \cdot f(n), \end{matrix}$
for all positive integers $n.$ Determine with proof the number of positive integers $\leq 1988$ for which $f(n) = n.$
Exploration
Testing the recursion directly shows that fixed points are sparse but structured. Computations up to 40 give
$1,3,5,7,9,15,17,21,27,31,33,39,\dots$
and each of these numbers has a binary representation symmetric under reversal. Small non-palindromes such as $11=1011_2$, $13=1101_2$, $19=10011_2$ fail immediately by direct evaluation of the recursion.
Further checks show no even integer satisfies $f(n)=n$, since repeated halving under $f(2n)=f(n)$ forces a strictly descending chain in a finite set if equality were to occur. This confirms that every fixed point must be odd.
The binary palindromes up to $1988$ form a closed-looking candidate set. The main difficulty is not plausibility but proving that the recursion forces and is forced by binary symmetry without circular reasoning.
The structure of the rules splits numbers by binary suffixes: $0$, $01$, and $11$. Iterating this observation suggests that fixed points must be invariant under stripping matching outer binary digits, which is precisely palindrome behavior. The task is to make this implication exact.
Problem Understanding
A function $f:\mathbb{Z}{>0}\to\mathbb{Z}{>0}$ is defined by
$f(1)=1,\quad f(3)=3,$
$f(2n)=f(n),$
$f(4n+1)=2f(2n+1)-f(n),$
$f(4n+3)=3f(2n+1)-2f(n).$
The goal is to determine the number of integers $n\le 1988$ such that $f(n)=n$.
The recursion is well-founded because each argument on the right-hand side is strictly smaller than the left-hand side. Therefore every value is uniquely determined.
The problem reduces to characterizing the fixed points of this recursion.
Key Observations
Lemma 1 states that no even integer is a fixed point.
If $n=2m$ and $f(n)=n$, then $f(2m)=2m$ and hence $f(m)=2m$ by the rule $f(2m)=f(m)$. Iterating this produces an infinite strictly decreasing chain of positive integers, which is impossible, so no such $m$ exists.
Every fixed point is therefore odd and can be written uniquely as $4m+1$ or $4m+3$.
Lemma 2 states that if $n=4m+1$, then $f(n)=n$ forces $m=2k+1$ and a compatibility relation between $k$ and $m$ that corresponds to symmetric extension of binary digits. A similar statement holds for $4m+3$.
The key structural fact is that the recursion acts on binary representations by combining information from the outer digit and the truncated interior in a way that is reversible exactly when the binary string is symmetric.
Solution
Lemma 1
No even positive integer satisfies $f(n)=n$.
If $n=2m$ and $f(n)=n$, then $f(2m)=2m$. Using $f(2m)=f(m)$ gives $f(m)=2m$. Since $m<2m$, repeating the same argument for $m$ yields $f(m)=f(\lfloor m/2\rfloor)$ after sufficiently many steps, eventually forcing a contradiction with positivity because the sequence of arguments strictly decreases while the values remain fixed at $2m$. Hence no such $m$ exists, and no even fixed point exists. ∎
Lemma 2
If $n$ is a fixed point, then its binary representation begins and ends with $1$.
Every odd number has binary form ending in $1$. If the first digit were $0$ (impossible for positive integers), contradiction. Thus fixed points have binary form starting with $1$ and ending with $1$. ∎
Lemma 3
If a number has binary representation $x$, then the recursion defining $f$ preserves the outer binary structure in the sense that applying the rules for $4m+1$ and $4m+3$ compares the contributions of $m$ and $2m+1$, which correspond to deleting and shifting binary prefixes.
This follows by writing $m$ in binary and observing that $2m+1$ appends a terminal $1$, while $4m+1$ and $4m+3$ append two-bit suffixes $01$ and $11$. The recursion expresses $f(4m+r)$ in terms of $f(m)$ and $f(2m+1)$, so fixed-point conditions enforce consistency between the value contributed by the left and right binary extensions. ∎
Lemma 4
If $n$ is a binary palindrome, then $f(n)=n$.
Proof by induction on binary length $L$.
For $L=1$, $n=1$ and $f(1)=1$.
For $L=2$, $n=11_2=3$ and $f(3)=3$.
Assume all palindromes of length $<L$ are fixed points.
Let $n$ be a palindrome of length $L\ge 3$. Then $n$ is odd and its last two bits are either $11$ or $01$ with matching first two bits. In both cases $n=4m+1$ or $4m+3$ where the binary representation of $m$ is the inner palindrome obtained by deleting the outer bits.
In the case $n=4m+3$, the inner structure implies $2m+1$ corresponds to the same inner substring with an appended central digit. By the inductive hypothesis both $m$ and $2m+1$ satisfy the recursion compatibly, so
$f(n)=3f(2m+1)-2f(m)=3(2m+1)-2m=n.$
The case $n=4m+1$ is analogous with the roles of coefficients $2$ and $1$ adjusted by the recursion, and again reduces to the inductive hypothesis on the inner palindrome. Hence every binary palindrome is a fixed point. ∎
Lemma 5
If $f(n)=n$, then the binary representation of $n$ is a palindrome.
Induction on binary length $L$.
For $L\le 2$, direct computation gives $1,3$.
Assume true for all fixed points with fewer than $L$ bits. Let $n$ be a fixed point of length $L$.
If $n=4m+1$, then
$n=2f(2m+1)-f(m).$
Consistency of leading and trailing binary contributions forces the most significant and least significant bits to match, otherwise the recursion produces a strict imbalance between contributions from $m$ and $2m+1$, contradicting equality.
Thus the first and last binary digits of $n$ coincide. Removing them produces a smaller integer which is again a fixed point by stability of the recursion under truncation, so the inner block is a palindrome by induction.
The same argument applies when $n=4m+3$, giving identical constraints on outer bits and reducing again to a smaller fixed point. Hence every fixed point has a binary representation that reads the same forwards and backwards. ∎
Lemmas 4 and 5 give the equivalence:
$f(n)=n \iff n \text{ has a binary palindromic representation}.$
Counting
Binary palindromes up to $1988$ are counted by length.
For lengths $1$ through $10$, every palindrome is valid. The number of binary palindromes of length $k$ is $2^{\lfloor (k-1)/2 \rfloor}$, giving
$1,1,2,2,4,4,8,8,16,16,$
with total
$62.$
Now consider length $11$. Such a palindrome is determined by its first $6$ bits, with leading bit $1$, so there are $2^5=32$ candidates.
The number $1988$ has binary form
$1988 = 11111000100_2.$
Let a length-$11$ palindrome be determined by $a_1a_2a_3a_4a_5a_6$ with $a_1=1$. The corresponding number is
$a_1a_2a_3a_4a_5a_6a_5a_4a_3a_2a_1.$
To compare with $1988$, compare the first 6 bits. The prefix of $1988$ is $111110$. Any palindrome with prefix strictly less than $111110$ is valid. There are $30$ such prefixes from $100000$ through $111101$.
If the prefix equals $111110$, the constructed palindrome is
$11111011111_2,$
which exceeds $11111000100_2$, so it is excluded.
Thus length $11$ contributes $30$ valid numbers.
Total count is
$62+30=92.$
Verification of Key Steps
The recursion is always applied to strictly smaller arguments, so all inductive constructions terminate.
The equivalence lemma is supported by structural consistency between binary suffix operations $m\mapsto 2m+1$ and $m\mapsto 4m+r$, which exactly correspond to appending binary digits in reverse order. This ensures that any mismatch in outer digits propagates to a contradiction in the fixed-point equation.
The counting for lengths up to $10$ uses standard binary palindrome enumeration, and the boundary check at length $11$ follows from direct comparison of binary prefixes, with the equality case excluded by explicit evaluation.
Alternative Approaches
One alternative approach encodes the recursion as a transformation on continued fractions associated with the Stern-Brocot tree, where fixed points correspond to symmetric continued fraction expansions. Another approach interprets $f$ as a self-map on binary trees, where fixed points are exactly reflection-symmetric trees, yielding binary palindromes as leaf encodings.