给定集合 $A_n=\{1,2,3,\cdots,n\}$,映射 $f: A_n \mapsto A_n$ 满足:
① 当 $i,j \in A_n $,$i\neq j$ 时,$f(i) \neq f(j)$;
② 任取 $m \in A_n$,若 $m \geqslant 2$,则有 $m \in \{f(1),f(2),\cdots,f(m)\}$.
则称映射 $f: A_n \mapsto A_n$ 是一个“优映射”.
例如:用下表表示的映射 $f: A_3 \mapsto A_3$ 是一个“优映射”.\[\begin{array}{|c|c|c|c| } \hline i&1&2&3 \\ \hline f\left(i\right)&2&3&1 \\ \hline \end{array}\]$(1)$ 已知下表表示的映射 $f: A_4 \mapsto A_4 $ 是一个“优映射”,请把表补充完整(只需填出一个满足条件的映射);\[\begin{array}{|c|c|c|c|c| } \hline i&1&2&3&4 \\ \hline f\left(i\right)& &3& & \\ \hline \end{array}\]$(2)$ 若映射 $f: A_{2010} \mapsto A_{2010} $ 是“优映射”,且 $f(1004)=1$,则 $f(1000)+f(1007)$ 的最大值是 
$(3)$ 若映射 $f: A_{10} \mapsto A_{10} $ 是“优映射”,且方程 $f(i)=i$ 的解恰有 $6$ 个,则这样的“优映射”的个数是 
【难度】
【出处】
【标注】
  • 题型
    >
    组合数学
    >
    组合计数
  • 知识点
    >
    函数
    >
    集合与映射
    >
    映射
【答案】
$(1)$ $2,1,4$ 或 $2,4,1$;$(2)$ $2011$;$(3)$ $84$
【解析】
$(1)$ 理解“优映射”的定义后容易填出符合条件的映射:\[\begin{array}{|c|c|c|c|c| } \hline i&1&2&3&4 \\ \hline f\left(i\right)&2 &3&1 & 4\\ \hline \end{array}\]\[\begin{array}{|c|c|c|c|c| } \hline i&1&2&3&4 \\ \hline f\left(i\right)&2 &3& 4&1 \\ \hline \end{array}\]$(2)$ 在上面的例子中 $f(3)=1$,我们发现 $f(4)=4$,据此进行下一步的探索.如图,$f(3)=1$,该如何填表呢?\[\begin{array}{|c|c|c|c|c| } \hline i&1&2&3&4 \\ \hline f\left(i\right)& & &1 & \\ \hline \end{array}\]如果 $f(1)$ 填 $4$,那么 $f(2)$ 只能填 $2$,在考虑 $m=3$ 时出现矛盾.
因此 $f(1)$ 只能填 $2$ 或 $3$,$f(2)$ 填 $2,3$ 中剩下的那个,$f(4)$ 只能填 $4$.
那么就有加长表格后,即当 $n>4$ 时,$f(i)=i$($i \geqslant 4$).
猜想:若 $f(k)=1$,则当 $i\geqslant k+1$ 时,$f(i)=i$.
证明如下:当 $\forall m \leqslant k$,$m\geqslant 2$,$m \in \mathbb N^*$ 时,$m \in \{f(1),f(2),\cdots,f(k)\}$.
于是$$\{2,3,\cdots, k\}\subseteq \{f(1),f(2),\cdots,f(k)\}.$$由于 $f(k)=1$,因此$$ \{f(1),f(2),\cdots,f(k-1)\}=\{2,3,\cdots, k\}.$$这就有当 $i\geqslant k+1$ 时,$f(i)=i$.
到这里,我们就很清楚 $f(1004)=1$ 的含义了.
一方面,$f(1007)=1007$;
另一方面,$f(1000)\in \{1,2,3,\cdots,1004\}$,所以 $f(1000)\leqslant 1004$.
接下来考查等号是否可以取到.
若 $f(1000)= 1004$,则可以如图填表.\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c| } \hline i&1&2&3&{\cdots}&p&{\cdots}&998&999&1000&1001&1002&1003&1004 \\ \hline f\left(i\right)&1000&2 &3&{\cdots}&p&{\cdots}&998&999&1004&1001&1002&1003&1 \\ \hline \end{array}\]因此等号可以取到,$f(1000)+f(1007)$ 的最大值为 $2011$.
⑶ 在⑵中验证等号是否能够取到的例子里,我们把所有满足 $f(i)=i$ 的列忽略,可以发现:\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c| } \hline i&1&2&3&{\cdots}&p&{\cdots}&998&999&1000&1001&1002&1003&1004 \\ \hline f\left(i\right)&1000&2 &3&\cdots&p&\cdots&998&999&1004&1001&1002&1003&1 \\ \hline \end{array}\]只要有一个基础的“错排”($f(i)\neq i$)就可以往里添加“等列”($f(i)=i$).
于是问题转化为先探索基础的 $4$ 列“错排”和如何添加 $6$ 列“等列”.
尝试后发现基础的 $4$ 列“错排”只有一个(事实上任意 $k$ 列“错排”都只有一个):\[\begin{array}{|c|c|c|c|c| } \hline i&1&2&3&4 \\ \hline f\left(i\right)&2 &3& 4&1 \\ \hline \end{array}\]即\[\begin{array}{|c|c|c|c|c| } \hline i&a&b&c&d \\ \hline f\left(i\right)&b &c& d&a\\ \hline \end{array}\]接下来添加 $6$ 列“等列”,其本质就是在 $10$ 列中选择“等列”的位置.由于只有第一列不能为“等列”,于是所求的“优映射”有 ${\mathrm C}_9^6=84$ 个.
题目 答案 解析 备注
0.126355s