每日一题[698]映射中的计数问题

给定集合$A_n=\{1,2,3,\cdots ,n\}$，映射$f:A_n\to A_n$满足：
(1)当$i,j\in A_n$，$i\ne j$时，$f(i)\ne f(j)$；
(2)任取$m\in A_n$，若$m\geqslant 2$，则有$m\in \left\{f(1),f(2),\cdots ,f(m)\right\}$．
则称映射$f:A_n\to A_n$是一个优映射．
(1) 当$n=4$时，若$f(2)=3$，写出一个符合条件的优映射：$f(1)=$_____，$f(3)=$_____；
(2) 若映射$f:A_{2010}\to A_{2010}$是优映射，且$f(1004)=1$，则$f(1000)+f(1007)$的最大值为_____；
(3) 若映射$f:A_{10}\to A_{10}$是优映射，且方程$f(x)=x$的解恰有$6$个，则这样的优映射的个数是______．

---

答案　(1) $2,1$(或$2,4$)；(2) $2011$；(3) $84$．

分析与解　(1)由题意知$2\in\{f(1),f(2)\}$，所以$f(1)=2$．而$f(3)$没有限制．
(2) 先给出一个引理$1$：
若$f(k)=1$，则当$i=k+1,\cdots ,n$时，有$f(i)=i$．

于是$f(1007)=1007$，而$f(1000)\leqslant 1004$．下面说明等号可以取到：
构造一个$f$满足

$$f(1)=1000,f(1000)=1004,f(1004)=1,$$ 对于$i\ne 1,1000,1004$时，有$f(i)=i$，则$f$是优映射，故等号可以取到．

(3)再给出一个引理$2$：
一个优映射实际上是由一个$k(k\in\mathcal{N})$列错位排列

$$f(x_i)=\begin{cases} x_{i+1},&i=1,2,\cdots ,k-1,\\ x_1,&i=k,\end{cases}$$ 再穿插$n-k$列等列(即$f(x)=x$的列)组成．

注意到第一列不能为等列，因此所求的优映射的个数就是从剩下$9$列中选出$6$个等列，而不是等列的列对应的函数值唯一确定，所以共有${\rm C}_9^6=84$个优映射．

---

引理$1$证明　由优映射定义知

$$\{2,3,\cdots,k\}\subseteq\{f(1),f(2),\cdots,f(k)\},$$ 而$f(k)=1\notin\{2,3,\cdots,k\}$，所以 $$\{2,3,\cdots,k\}=\{f(1),f(2),\cdots,f(k-1)\},$$ 而$k+1\in\{f(1),f(2),\cdots,f(k),f(k+1)\}$，所以只能有 $$k+1=f(k+1),$$ 以此类推知，对任意的$i\geqslant k+1$，有$f(i)=i$．

---

引理$2$证明　当$f(1)=1$时，由引理$1$知，优映射全由等列构成；

当$f(1)\ne 1$，不妨设$f(k)=1,k>1$，则从第$k+1$列往后全为等列．
设前$k$列中不是等列的列有第$1,i_1,i_2,\cdots,i_m,k$列，其中$1<i_1<i_2<\cdots<i_m<k$．
由优映射定义知

$$i_1\in\{f(1),f(2),\cdots,f(i_1)\},$$ 因为$f(i_1)\ne i_1$，而其它列为等列，所以只能有$f(1)=i_1$．
类似地可以得到 $$f(i_1)=i_2,f(i_2)=i_3,\cdots,f(i_m-1)=i_m,f(i_m)=k.$$ 引理得证．

注　本题为2010年北京市海淀区二模选择题的最后一题．