Let be a set of functions defined for integers from to and taking integer values from to . Suppose that satisfies the following two conditions:
* For any function belonging to and any integers and with , we have .
* For any functions and belonging to and any integer from to , we have .
In this case, find the maximum possible number of elements of .
Solution
We say that is a fixed point of if we have . Suppose that a function belonging to has two fixed points and with . Then, it follows from the first condition that , which is a contradiction. Therefore, each function belonging to has at most one fixed point.
Suppose that is non-empty. Take a function belonging to , and define . Then, is a fixed point of since we have by the second condition. Let be a function belonging to . Then, we have
by the second condition. It shows that is also a fixed point of . By the uniqueness of the fixed point of , we conclude that . Therefore, we have proved that is the unique fixed point of any function belonging to .
Let and be functions belonging to , and an integer from to . Then, the second condition says that is a fixed point of , and hence, we have .
Let denote the set of integers from to such that holds for any function belonging to . Let be the smallest element of , and the largest element of . Then, for any function belonging to , we have by the first condition. Therefore, we conclude that is the set of integers from to . Note that we already proved that for any functions and belonging to and any integer from to . Therefore, we conclude that belongs to for such and . Summarizing the discussion here, it has been shown that belonging to satisfies both
We fix a function belonging to . For an integer from to , we define . Then, by (1), the sequence satisfies
Furthermore, by (2), we have for any integer from to . Therefore, for any function that belongs to , we can associate it with a method of choosing integers from the integers from to , such that all integers from to are chosen. Here, this choice corresponds to choosing integers from the integers that are from to but not between and . Hence, the number of such choice is . Furthermore, since the methods of choosing corresponding to different functions belonging to are distinct, the number of elements in is at most . In addition, for a positive integer from to , we have
which implies
Therefore, we can conclude that the number of elements in is at most .
On the other hand, consider the set of functions that are defined for integers from to and take integer values from to , and satisfy
This set satisfies the first condition. Furthermore, for any functions and in and any integer from to , we have , so holds. Thus, the second condition is also satisfied. By considering and in the argument above, we see that there is a one-to-one correspondence between the functions in and the sequences of integers satisfying
Therefore, the number of elements in is .
Therefore, we conclude that the maximum possible number of elements in is .