uniolympiads Ελληνικά

IMC 1998, Day 2, Problem 4

Let An={1,2,…,n}A_n = \{1, 2, \dots, n\}, where n≥3n \ge 3. Let F\mathcal{F} be the family of all non-constant functions f ⁣:An→Anf\colon A_n \to A_n satisfying the following conditions:

(1) f(k)≤f(k+1)f(k) \le f(k+1) for k=1,2,…,n−1k = 1, 2, \dots, n-1,

(2) f(k)=f(f(k+1))f(k) = f(f(k+1)) for k=1,2,…,n−1k = 1, 2, \dots, n-1.

Find the number of functions in F\mathcal{F}.

Original from the official PDF(20 points) Let A n = {1, 2, . . . , n}, where n ≥ 3. Let F be the family of all non-constant functions f : A n → A n satisfying the following conditions: (1) f (k) ≤ f (k + 1) for k = 1, 2, . . . , n − 1, (2) f (k) = f (f (k + 1)) for k = 1, 2, . . . , n − 1. Find the number of functions in F.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. It is clear that id:An⟶Anid : A_n \longrightarrow A_n, given by id(x)=xid(x) = x, does not verify condition (2). Since idid is the only increasing injection on AnA_n, F\mathcal{F} does not contain injections. Let us take any f∈Ff \in \mathcal{F} and suppose that #(f−1(k))≥2\#\left(f^{-1}(k)\right) \ge 2. Since ff is increasing, there exists i∈Ani \in A_n such that f(i)=f(i+1)=kf(i) = f(i + 1) = k. In view of (2), f(k)=f(f(i+1))=f(i)=kf(k) = f\left(f(i + 1)\right) = f(i) = k. If {i<k:f(i)<k}=∅\{i < k : f(i) < k\} = \emptyset, then taking j=max⁡{i<k:f(i)<k}j = \max\{i < k : f(i) < k\} we get f(j)<f(j+1)=k=f(f(j+1))f(j) < f(j + 1) = k = f\left(f(j + 1)\right), a contradiction. Hence f(i)=kf(i) = k for i≤ki \le k. If #(f−1({l}))≥2\#\left(f^{-1}(\{l\})\right) \ge 2 for some l≥kl \ge k, then the similar consideration shows that f(i)=l=kf(i) = l = k for i≤ki \le k. Hence #(f−1{i})=0\#\left(f^{-1}\{i\}\right) = 0 or 1 for every i>ki > k. Therefore f(i)≤if(i) \le i for i>ki > k. If f(l)=lf(l) = l, then taking j=max⁡{i<l:f(i)<l}j = \max\{i < l : f(i) < l\} we get f(j)<f(j+1)=l=f(f(j+1))f(j) < f(j + 1) = l = f\left(f(j + 1)\right), a contradiction. Thus, f(i)≤i−1f(i) \le i - 1 for i>ki > k. Let m=max⁡{i:f(i)=k}m = \max\{i : f(i) = k\}. Since ff is non-constant m≤n−1m \le n - 1. Since k=f(m)=f(f(m+1))k = f(m) = f\left(f(m + 1)\right), f(m+1)∈[k+1,m]f(m + 1) \in [k + 1, m]. If f(l)>l−1f(l) > l - 1 for some l>m+1l > m + 1, then l−1l - 1 and f(l)f(l) belong to f−1(f(l))f^{-1}\left(f(l)\right) and this contradicts the facts above. Hence f(i)=i−1f(i) = i - 1 for i>m+1i > m + 1. Thus we show that every function ff in F\mathcal{F} is defined by natural numbers k,l,mk, l, m, where 1≤k<l=f(m+1)≤m≤n−11 \le k < l = f(m + 1) \le m \le n - 1.

f(i)={kif i≤mlif i=mi−1if i>m+1.f(i) = \begin{cases} k & \text{if } i \le m \\ l & \text{if } i = m \\ i - 1 & \text{if } i > m + 1. \end{cases}

Then

#(F)=(n3).\#(\mathcal{F}) = \begin{pmatrix} n \\ 3 \end{pmatrix}.

Transcribed from the official solutions, pages 2–3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?