IMO 1988 Problem 3: Recursive Function Fixed Points f(n) = n Explained

IMO 1988 Problem 3 — First Look

We’ll save IMO 1988 Problem 6 for another time. For now, let’s take a look at Problem 3. The statement appears deceptively straightforward — share your thoughts on how you would approach it.

The Problem Statement

Problem 3.
A function f is defined on the positive integers as follows:

f(1) = 1,
f(3) = 3,
f(2n) = f(n),
f(4n + 1) = 2f(2n + 1) − f(n),
f(4n + 3) = 3f(2n + 1) − 2f(n),

for all positive integers n.

Fixed Points of the Recursive Function: The Question

Find the number of positive integers n, less than or equal to 1988, for which f(n) = n.