74th 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 $\left(\genfrac{}{}{0ex}{}{n-1}{0}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n-1}{n-k}\right)$ (these are the possibilities of placing $0,1,2,\dots ,n-k$ of $1$). Therefore: $$\begin{gathered} |\mathcal{F}|=\sum _{k=1}^n\left(\left(\genfrac{}{}{0ex}{}{n-1}{0}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n-1}{n-k}\right)\right)=\sum _{p=0}^{n-1}(n-p)\left(\genfrac{}{}{0ex}{}{n-1}{p}\right)= \\ =n\cdot 2^{n-1}-(n-1)\sum _{p=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n-2}{p-1}\right)=(n+1)2^{n-2}. \end{gathered}$$

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}$.

---

Alternative solution.

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)+\cdots +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 \cdots \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}.$$

---

Alternative solution.

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{array}{rl}|\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{array}$$

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}.$$