Library / Bulgarian Mathematical Competitions /16 of 92

Bulgarian Mathematical Competitions

Combinatorics Difficulty 5.2 AIME, harder Prove it Bulgaria

Problem:
Let $A=\{1,2, \ldots, n\}, n \geq 4$ . For any function $f: A \rightarrow A$ and any $a \in A$ define $f_{1}(a)=f(a)$ , $f_{i+1}(a)=f\left(f_{i}(a)\right)$ , $i \geq 1$ . Find the number of the functions $f$ such that $f_{n-2}$ is a constant function but $f_{n-3}$ is not.

Solution

Solution:
Define an oriented graph $G$ with vertices the elements of $A$ and oriented edge $xy$ if $f(x)=y$ . We have to count the graphs $G$ such that:
- there are no cycles with length greater than $1$ ;
- there is a chain $a_{2} \ldots a_{n}$ with length $n-2$ and there is no chain with length $n-1$ ;
- the only edge outside this chain has the form $a_{1} a_{j}$ , where $3 \leq j \leq n$ ;
- there is a unique loop $a_{n} a_{n}$ .
The chain can be chosen in $n!$ ways, and the edge outside it - in $n-2$ ways. Note that the graphs for which this edge is $a_{1} a_{3}$ , are counted two times and hence their number is equal to $\binom{n}{2}(n-2)!$ . So the answer of the problem is
$n!(n-2)-\binom{n}{2}(n-2)!=\frac{n!(2n-5)}{2}$

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.