MathDB
Functional equation - f_n(x) = x

Source:

September 2, 2010
algebrafunctional equationDivisibilityrecurrence relationIMO ShortlistIMO Longlist

Problem Statement

Let Sn={1,2,⋯ ,n}S_n = \{1, 2,\cdots, n\} and fn:Sn→Snf_n : S_n \to S_n be defined inductively as follows: f1(1)=1,fn(2j)=j (j=1,2,⋯ ,[n/2])f_1(1) = 1, f_n(2j) = j \ (j = 1, 2, \cdots , [n/2]) and
* if n=2k (k≥1)n = 2k \ (k \geq 1), then fn(2j−1)=fk(j)+k (j=1,2,⋯ ,k);f_n(2j - 1) = f_k(j) + k \ (j = 1, 2, \cdots, k);
* if n=2k+1 (k≥1)n = 2k + 1 \ (k \geq 1), then fn(2k+1)=k+fk+1(1),fn(2j−1)=k+fk+1(j+1) (j=1,2,⋯ ,k).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 fn(x)=xf_n(x) = x if and only if xx is an integer of the form (2n+1)(2d−1)2d+1−1\frac{(2n + 1)(2^d - 1)}{2^{d+1} - 1} for some positive integer d.d.
Back to ProblemsView on AoPS