ILL 1992 Problem 32

Let $S_n = \{1, 2,\cdots, n\}$ and $f_n : S_n \to S_n$ be defined inductively as follows: $f_1(1) = 1, f_n(2j) = j \ (j = 1, 2, \cdots , [n/2])$ and

• (i) if $n = 2k \ (k \geq 1)$ , then $f_n(2j - 1) = f_k(j) + k \ (j = 1, 2, \cdots, k);$
• (ii) if $n = 2k + 1 \ (k \geq 1)$ , then $f_n(2k + 1) = k + f_{k+1}(1), f_n(2j - 1) = k + f_{k+1}(j + 1) \ (j = 1, 2,\cdots , k).$

Prove that $f_n(x) = x$ if and only if $x$ is an integer of the form $$\frac{(2n + 1)(2^d - 1)}{2^{d+1} - 1}$$ for some positive integer $d.$