Romanian Mathematical Olympiad

a) We count the functions in $\mathcal{F}$ with $f(1) = k$, $k = 1, \dots, n$. We associate to each $i = 2, \dots, n$ the number $f(i)-f(i-1) \in \{0, 1\}$, with the restriction that there can be at most $n-k$ occurrences of $1$. This association is bijective, and the number of possibilities of choosing the numbers $0$ and $1$ as described above is $\binom{n-1}{0} + \binom{n-1}{1} + \dots + \binom{n-1}{n-k}$ (these are the possibilities of placing $0, 1, 2, \dots, n-k$ of $1$). Therefore:
$$|\mathcal{F}| = \sum_{k=1}^{n} \left( \binom{n-1}{0} + \binom{n-1}{1} + \dots + \binom{n-1}{n-k} \right) = \sum_{p=0}^{n-1} (n-p) \binom{n-1}{p} = \\ = n \cdot 2^{n-1} - (n-1) \sum_{p=0}^{n-1} \binom{n-2}{p-1} = (n+1)2^{n-2}.$$

b) We count how many times the fixed point $k$ appears in the functions from $\mathcal{F}$, $k = 1, \dots, n$ (the same fixed point may appear in multiple functions). We associate to each function for which $f(k) = k$ the numbers $f(i) - f(i-1) \in \{0, 1\}, i = 2, \dots, n$.
Since these numbers can be chosen without restrictions, there are $2^{n-1}$ possibilities. Thus, each fixed point appears in $2^{n-1}$ functions, and $\sum_{f \in \mathcal{F}} |\text{Fix}(f)| = n \cdot 2^{n-1}$.

Let $\mathcal{F}_n$ be the set from the problem statement, and $k_n = |\mathcal{F}_n|$. Also, let $s_n = \sum_{f \in \mathcal{F}_n} |\text{Fix}(f)|$. For $n=2$ we have $k_2 = 3$ and $s_2 = 4$.

a) We notice that if $f \in \mathcal{F}_{n+1}$ and $f(n) \le n$, then the restriction of $f$ to $\{1, 2, \dots, n\}$ is a function from $\mathcal{F}_n$. Conversely, any function from $\mathcal{F}_n$ can be extended to one in $\mathcal{F}_{n+1}$ in two ways, since $f(n+1) \in \{f(n), f(n)+1\}$.
For the case $f(n) = n+1$ we have $f(n+1) = n+1$, and then, going through the values $f(n-1), f(n-2), \dots, f(1)$, we observe that at each step $f(k+1) - f(k)$ can be $0$ or $1$, so we can construct $f$ in $2^{n-1}$ ways. Therefore, we have the recurrence $k_{n+1} = 2k_n + 2^{n-1}$, and since $k_2 = 3$, we obtain $k_n = (n+1) \cdot 2^{n-2}$.

b) Let $a_i(n)$ be the number of functions $f \in \mathcal{F}_n$ for which $i \in \text{Fix}(f)$. Then we have $s_n = a_1(n) + a_2(n) + \dots + a_n(n)$. Let $f \in \mathcal{F}_{n+1}$ be a function for which $f(k) = k$, for $k \le n$. Then, using the hypothesis relation, we have:
$$f(n) \le f(n-1) + 1 \le \dots \le f(k) + (n-k) = n.$$
Therefore, the restriction of $f$ to $\{1, 2, \dots, n\}$ is a function from $\mathcal{F}_n$, i.e., $f$ is obtained from a function from $\mathcal{F}_n$, to which the value $f(n+1)$ is added. But, since $f(n) \le n$, the value of $f(n+1)$ can be chosen in two ways, which implies $a_k(n+1) = 2a_k(n)$, for any $k \le n$.
To determine $a_{n+1}(n+1)$, we observe that $f(n+1) = n+1$, and going through the values $f(n), f(n-1), \dots, f(1)$, we observe that at each step $f(k+1) - f(k)$ is $0$ or $1$, i.e., $f$ can be constructed in $2^n$ ways. Therefore, $a_{n+1}(n+1) = 2^n$.
From here we have the recurrence $s_{n+1} = 2s_n + 2^n$, and since $s_2 = 4$, we obtain
$$s_n = n \cdot 2^{n-1}.$$

We observe that if $f(\ell) = \ell = f(\ell - 1)$, then there are no fixed points of the function $f \in \mathcal{F}$ smaller than $\ell$. Similarly, if $f(\ell) = \ell = f(\ell + 1)$, then there are no fixed points of $f \in \mathcal{F}$ greater than $\ell$. From here we deduce that the fixed points of a function $f \in \mathcal{F}$ form a set of $k$ consecutive numbers $\{\ell, \ell+1, \dots, \ell+k-1\}$.

We characterize the functions in $\mathcal{F}$ that have $k \le n - 2$ fixed points.
For $2 \le \ell \le n-k$, we have $f(\ell - 1) = \ell$ and $f(\ell + k) = \ell + k - 1$. Now for $\{f(1), f(2), \dots, f(\ell - 2)\}$ we have $2^{\ell-2}$ ways to construct the function $f$, and for $\{f(\ell + k + 1), \dots, f(n)\}$ we have $2^{n-\ell-k}$ ways to construct $f$, so in total we have $2^{n-k-2}$ ways to construct $f$ in this case.
For $\ell = 1$ or $\ell = n-k+1$, we have fixed only one more point besides the $k$ fixed points, so $f$ can be constructed in $2^{n-k-1}$ ways. Therefore, in total we have $(n-k+3) \cdot 2^{n-k-2}$ functions in $\mathcal{F}$ having $k \le n-2$ fixed points. For $k = n-1$ fixed points, we have only two such functions in $\mathcal{F}$, and for $k = n$ fixed points, we have only one function in $\mathcal{F}$.

a) From the above, we deduce:
$$\begin{align*} |\mathcal{F}| &= 3 + \sum_{k=1}^{n-2} (n-k+3) \cdot 2^{n-k-2} = 3 + \sum_{k=1}^{n-2} 2^{n-k-2} + \sum_{k=1}^{n-2} (n-k-1)2^{n-k-2} \\ &= \sum_{k=0}^{n-1} 2^k + \sum_{k=0}^{n-3} (k+1)2^k = 2^n - 1 + (n-1) \cdot 2^{n-2} - 2^{n-1} + 1 \\ &= (n+1) \cdot 2^{n-2}. \end{align*}$$

b) Similarly, we deduce:
$$\sum_{f \in \mathcal{F}} |\text{Fix}(f)| = 3n-2 + \sum_{k=1}^{n-2} k(n-k+3) \cdot 2^{n-k-2} = n \cdot 2^{n-1}.$$