每日一题[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$个,则这样的优映射的个数是______.


cover

答案 (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年北京市海淀区二模选择题的最后一题.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表评论