1996 IMO Problems/Problem 3
Problem
Let denote the set of nonnegative integers. Find all functions from to itself such that
Solution
Plugging in m = 0, we get f(f(n)) = f(n) . With m = n = 0, we get f(0) = 0.
If there are no fixed points of this function greater than , then , which is a valid solution.
Let be the smallest fixed point of such that . . Plugging , we get .
By an easy induction, we get .
Let be another fixed point greater than .
Let , where .
So, .
. But, . This means that the set of all fixed points of is .
Let and . So, . So, is also a fixed point, which means that the functional values of non-fixed points are permutations of the fixed points. So let , where .
Now let , where .
So .
So there are two general solutions, (where the only fixed point is 0) or where is the smallest fixed point greater than 0 (in the second case), where and q is the quotient when is divided by .
See Also
1996 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |