Maths Olympiad Prep

Library / /121 of 121

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it India

A finite set SS of positive integers is called cardinal if SS contains the integer S|S|, where S|S| denotes the number of distinct elements in SS. Let ff be a function from the set of positive integers to itself, such that for any cardinal set SS, the set f(S)f(S) is also cardinal. Here f(S)f(S) denotes the set of all integers that can be expressed as f(a)f(a) for some aa in SS. Find all possible values of f(2024)f(2024).
Note: As an example, {1,3,5}\{1, 3, 5\} is a cardinal set because it has exactly 3 distinct elements, and the set contains 3.

Solutions — 2

Solution 1

Solution 1. The possible values are 1, 2, and 2024.

Construction. The function f(x)=1f(x) = 1 for all xNx \in \mathbb{N} works. Also, f(x)=1f(x) = 1 for all x2024x \neq 2024 and f(2024)=2f(2024) = 2, works. Finally, f(x)=xf(x) = x for all xNx \in \mathbb{N} works as well.
It remains to show these are the only possible values for f(2024)f(2024).

Proof. Denote Im(f)={f(x)xN}\text{Im}(f) = \{f(x) \mid x \in \mathbb{N}\}. The cardinal set {1}\{1\} gives f(1)=1f(1) = 1. Consider the following two cases:

* Im(f)\text{Im}(f) is unbounded. Fix any nNn \in \mathbb{N}, with n>1n > 1. Pick n1n-1 distinct integers k1,,kn1k_1, \dots, k_{n-1} such that f(ki){n,f(n)}f(k_i) \notin \{n, f(n)\} and f(ki)f(k_i) are all pairwise distinct, for 1i<n1 \le i < n. Then {n,k1,,kn1}\{n, k_1, \dots, k_{n-1}\} is a cardinal set. Then {f(n),f(k1),,f(kn1)}\{f(n), f(k_1), \dots, f(k_{n-1})\} is a cardinal set with nn distinct elements, so nn lies in this set, hence f(n)=nf(n) = n. This gives the identity function.

* Im(f)\text{Im}(f) is bounded. Suppose f(x)Mf(x) \le M for all xNx \in \mathbb{N} and some integer M>0M > 0.

Claim. For any integer aa satisfying 1aM1 \le a \le M, if there are infinitely many integers nNn \in \mathbb{N} such that f(n)=af(n) = a, then a=1a = 1.

Proof. Let b>1b > 1 be one of the integers with f(b)=af(b) = a. Consider b1b-1 other integers c1,,cb1c_1, \dots, c_{b-1}, such that f(ci)=af(c_i) = a for 1i<b1 \le i < b, and cic_i are all pairwise distinct. Then {b,c1,,cb1}\{b, c_1, \dots, c_{b-1}\} is a cardinal set, so the image set, which consists of the singleton {a}\{a\} is cardinal, hence a=1a = 1. \square

So for every 2mM2 \le m \le M, there are only finitely many integers xx such that f(x)=mf(x) = m. Thus, there exists an integer N>1N > 1 such that for all nNn \ge N, f(n)=1f(n) = 1. Now for every 1<l<N1 < l < N, consider the cardinal set {l,N+1,N+2,,N+l1}\{l, N+1, N+2, \dots, N+l-1\}. Then the image set consists of {1,f(l)}\{1, f(l)\}, which can be cardinal only when f(l)=1f(l) = 1 or f(l)=2f(l) = 2.

By the above reasoning, f(2024)f(2024) can only be 1, 2, or 2024, each of which occurs as an example. \square

Solution 2

Solution 2. We present a second proof of the fact that the proposed values are the only possibilities. Considering the singleton cardinal set {1}\{1\}, we see that f(1)=1f(1) = 1. The cardinal set {1,2}\{1, 2\} gets mapped to {1,f(2)}\{1, f(2)\}, so f(2)f(2) must be 2 or 1.

Case 1. Suppose f(2)=1f(2) = 1. Now {2,2024}\{2, 2024\} is a cardinal set, and therefore so is {1,f(2024)}\{1, f(2024)\}. This means f(2024)f(2024) is 1 or 2.

Case 2. Suppose f(2)=2f(2) = 2. The cardinal set f({1,2,3})={1,2,f(3)}f(\{1, 2, 3\}) = \{1, 2, f(3)\} shows that f(3){1,2,3}f(3) \in \{1, 2, 3\}, but the cardinal set f({2,3})={2,f(3)}f(\{2, 3\}) = \{2, f(3)\} proves f(3)f(3) cannot be 2. Thus there are two sub-cases:

2.1. f(3)=1f(3) = 1. Then the set {1,3,2024}\{1, 3, 2024\} is cardinal, hence so is {1,f(2024)}\{1, f(2024)\}, implying, as before, f(2024){1,2}f(2024) \in \{1, 2\}.

2.2. f(3)=3f(3) = 3. In this case, we show via induction that f(n)=nf(n) = n for all nNn \in \mathbb{N}.

The base cases n=1,2,3n = 1, 2, 3 are already known. Now consider n4n \ge 4, and assume f(k)=kf(k) = k for all k<nk < n. Consider the cardinal f({1,2,,n})={1,2,,n1,f(n)}f(\{1, 2, \dots, n\}) = \{1, 2, \dots, n-1, f(n)\} which implies f(n){1,2,,n}f(n) \in \{1, 2, \dots, n\}.

However, consider the n1n-1-element cardinal set {1,2,,n}{n2}\{1, 2, \dots, n\} \setminus \{n-2\}. For its image to be cardinal f(n)f(n) cannot equal any number in {1,2,,n1}{n2}\{1, 2, \dots, n-1\} \setminus \{n-2\}; else its cardinality would be n2n-2, which isn't in the set. So f(n){n2,n}f(n) \in \{n-2, n\}.

Finally, consider the n2n-2-element set {1,2,,n}{n1,n3}\{1, 2, \dots, n\} \setminus \{n-1, n-3\}. If f(n)=n2f(n) = n-2, its image would only have n3n-3 elements, and thus would not be cardinal. So we conclude that f(n)=nf(n) = n and the induction is complete. In particular, f(2024)=2024f(2024) = 2024.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.