Problem 3. Let $n$ be a non-zero natural number and $A=\{1,2, \ldots, n\}$. Determine the number of increasing functions $f: A \rightarrow A$ with the property that $|f(x)-f(y)| \leq|x-y|$ for any $x, y \in A$.
Solution. We observe that $f(k+1)-f(k) \stackrel{\text { not }}{=} a_{k} \in\{0,1\}, k=1,2, \ldots, n-1$. 1 point

Moreover, if $a_{k} \in\{0,1\}$, then $|f(x)-f(y)| \leq|x-y|$ for any $x$, $y \in A .{ }^{2}$

1 point

By fixing $f(0)=a$ and $f(n)=b$, we have $b-a=a_{1}+\cdots+a_{n-1}$, so the number of functions $f$ with the desired property is equal to the number of ways to choose $b-a$ terms equal to 1 in the sum $a_{1}+\cdots+a_{n-1}$, i.e., $n(a, b)=C_{n-1}^{b-a}$.

Therefore, the number of functions is $\sum_{0 \leq a \leq b \leq n} n(a, b)=\sum_{0 \leq a \leq b \leq n} C_{n-1}^{b-a}=$ $\sum_{k=0}^{n-1}(n-k) C_{n-1}^{k}$.

This results in $n 2^{n-1}-(n-1) 2^{n-2}=(n+1) 2^{n-2}$ functions.

1 point