IMO 1992 LL IRE32

Origin: IRE

Problem

Let Sn = {1, 2, . . ., n} and fn : Sn \toSn be defined inductively as follows: f1(1) = 1, fn(2j) = j (j = 1, 2, . . ., [n/2]) and (i) if n = 2k (k \geq1), then fn(2j −1) = fk(j) + k (j = 1, 2, . . ., k); (ii) if n = 2k + 1 (k \geq1), then fn(2k + 1) = k + fk+1(1), fn(2j −1) = k + fk+1(j + 1) (j = 1, 2, . . . , k). Prove that fn(x) = x if and only if x is an integer of the form (2n + 1)(2d −1) 2d+1 −1 for some positive integer d.