Maths Olympiad Prep

Library / /58 of 63

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Japan

Let AA be a set of functions defined for integers from 11 to 20232023 and taking integer values from 11 to 20232023. Suppose that AA satisfies the following two conditions:
* For any function ff belonging to AA and any integers xx and yy with 1x<y20231 \le x < y \le 2023, we have f(x)f(y)f(x) \ge f(y).
* For any functions ff and gg belonging to AA and any integer xx from 11 to 20232023, we have f(g(x))=g(f(g(x)))f(g(x)) = g(f(g(x))).
In this case, find the maximum possible number of elements of AA.

Solution

(20221011) \boxed{\binom{2022}{1011}}
We say that xx is a fixed point of ff if we have f(x)=xf(x) = x. Suppose that a function ff belonging to A\mathcal{A} has two fixed points aa and bb with a<ba < b. Then, it follows from the first condition that a=f(a)f(b)=ba = f(a) \ge f(b) = b, which is a contradiction. Therefore, each function belonging to A\mathcal{A} has at most one fixed point.

Suppose that A\mathcal{A} is non-empty. Take a function ff belonging to A\mathcal{A}, and define a=f(f(1))a = f(f(1)). Then, aa is a fixed point of ff since we have f(f(1))=f(f(f(1)))f(f(1)) = f(f(f(1))) by the second condition. Let gg be a function belonging to A\mathcal{A}. Then, we have
g(a)=g(f(a))=f(g(f(a)))=f(g(a)) g(a) = g(f(a)) = f(g(f(a))) = f(g(a))
by the second condition. It shows that g(a)g(a) is also a fixed point of ff. By the uniqueness of the fixed point of ff, we conclude that g(a)=ag(a) = a. Therefore, we have proved that aa is the unique fixed point of any function gg belonging to A\mathcal{A}.
Let ff and gg be functions belonging to A\mathcal{A}, and xx an integer from 11 to 20232023. Then, the second condition says that f(g(x))f(g(x)) is a fixed point of gg, and hence, we have f(g(x))=af(g(x)) = a.
Let XX denote the set of integers xx from 11 to 20232023 such that f(x)=af(x) = a holds for any function ff belonging to A\mathcal{A}. Let \ell be the smallest element of XX, and mm the largest element of XX. Then, for any function ff belonging to A\mathcal{A}, we have a=f()f(+1)f(m)=aa = f(\ell) \ge f(\ell+1) \ge \dots \ge f(m) = a by the first condition. Therefore, we conclude that XX is the set of integers from \ell to mm. Note that we already proved that f(g(x))=af(g(x)) = a for any functions ff and gg belonging to A\mathcal{A} and any integer xx from 11 to 20232023. Therefore, we conclude that g(x)g(x) belongs to XX for such gg and xx. Summarizing the discussion here, it has been shown that ff belonging to A\mathcal{A} satisfies both
(1)mf(1)f(2)f(2023), and (1) \quad m \ge f(1) \ge f(2) \ge \dots \ge f(2023) \ge \ell, \text{ and}
(2)we have f(x)=a for any integer x from  to m. (2) \quad \text{we have } f(x) = a \text{ for any integer } x \text{ from } \ell \text{ to } m.
We fix a function ff belonging to A\mathcal{A}. For an integer xx from 11 to 20232023, we define sx=f(x)xs_x = f(x) - x. Then, by (1), the sequence s1,s2,,s2023s_1, s_2, \dots, s_{2023} satisfies
m1s1>s2>>s20232023. m - 1 \ge s_1 > s_2 > \dots > s_{2023} \ge \ell - 2023.
Furthermore, by (2), we have sx=axs_x = a - x for any integer xx from \ell to mm. Therefore, for any function that belongs to A\mathcal{A}, we can associate it with a method of choosing 20232023 integers from the integers from 2023\ell - 2023 to m1m - 1, such that all integers from ama - m to aa - \ell are chosen. Here, this choice corresponds to choosing 2023((a)(am)+1)=2022m+2023 - ((a - \ell) - (a - m) + 1) = 2022 - m + \ell integers from the 20222022 integers that are from 2023\ell - 2023 to m1m - 1 but not between ama - m and aa - \ell. Hence, the number of such choice is (20222022m+)\binom{2022}{2022 - m + \ell}. Furthermore, since the methods of choosing corresponding to different functions belonging to A\mathcal{A} are distinct, the number of elements in A\mathcal{A} is at most (20222022m+)\binom{2022}{2022 - m + \ell}. In addition, for a positive integer xx from 00 to 20212021, we have
(2022+1)(2022)=2022+1, \frac{\binom{2022}{\ell+1}}{\binom{2022}{\ell}} = \frac{2022 - \ell}{\ell+1},
which implies
(20220)<(20221)<<(20221010)<(20221011)>(20221012)>>(20222021)>(20222022). \binom{2022}{0} < \binom{2022}{1} < \dots < \binom{2022}{1010} < \binom{2022}{1011} > \binom{2022}{1012} > \dots > \binom{2022}{2021} > \binom{2022}{2022}.
Therefore, we can conclude that the number of elements in A\mathcal{A} is at most (20221011)\binom{2022}{1011}.
On the other hand, consider the set B\mathcal{B} of functions ff that are defined for integers from 11 to 20232023 and take integer values from 11 to 20232023, and satisfy
1012=f(1)=f(2)==f(1012)f(1013)f(1014)f(2023). 1012 = f(1) = f(2) = \dots = f(1012) \ge f(1013) \ge f(1014) \ge \dots \ge f(2023).
This set satisfies the first condition. Furthermore, for any functions ff and gg in B\mathcal{B} and any integer xx from 11 to 20232023, we have g(x)1012g(x) \le 1012, so f(g(x))=1012f(g(x)) = 1012 holds. Thus, the second condition is also satisfied. By considering =1\ell = 1 and a=m=1012a = m = 1012 in the argument above, we see that there is a one-to-one correspondence between the functions ff in B\mathcal{B} and the sequences s1,s2,,s2023s_1, s_2, \dots, s_{2023} of integers satisfying
s1=1011,s2=1010,,s1012=0,1s1013>s1014>>s20232022. s_1 = 1011, s_2 = 1010, \dots, s_{1012} = 0, \quad -1 \ge s_{1013} > s_{1014} > \dots > s_{2023} \ge -2022.
Therefore, the number of elements in B\mathcal{B} is (20221011)\binom{2022}{1011}.
Therefore, we conclude that the maximum possible number of elements in A\mathcal{A} is (20221011)\binom{2022}{1011}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.