每日一题[2201]一波三折

已知 $f$ 是从集合 $A=\{0,1,2,3,4,5,6\}$ 到整数集的映射,且 $ f (0) =0 $,$ f (6) =12 $,且对任意 $ x, y\in A $,都有\[ |x-y| \leqslant|f(x)-f(y)| \leqslant 3|x-y|,\]则符合要求的映射 $ f$ 的个数为_______.

答案    $185$.

解析    由于 $1\leqslant |f(n)-f(n+1)|\leqslant 3$,若 $f$ 递减了 $k$ 次,那么\[12=f(6)\leqslant -1\cdot k+3(6-k)=18-4k,\]因此 $f$ 最多递减 $1$ 次.

情形一       $f$ 递减次数为 $0$.此时 $f(n+1)-f(n)\in \{1,2,3\}$,设 $f(n+1)-f(n)$($n=0,1,2,3,4,5$)中递增 $1,2,3$ 的次数分别为 $a,b,c$.于是\[\begin{cases} a+b+c=6,\\ a+2b+3c=12,\end{cases}\implies b+2c=6,\]于是\[(b,c)=(6,0),(4,1),(2,2),(0,3),\]对应的 $a$ 分别为 $0,1,2,3$,对应的映射 $f$ 的个数为\[ \dbinom{6}{0~6~0}+\dbinom{6}{1~4~1}+\dbinom{6}{2~2~2}+\dbinom{6}{3~0~3}=1+30+90+20=141. \]

情形二     $f$ 递减次数为 $1$.如果递减发生在 $f(0)-f(1)$ 或 $f(5)-f(6)$,则 $f(2)$ 或 $f(4)$ 可以分别确定.于是\[\begin{cases} a+b+c=4,\\ a+2b+3c=10,\end{cases}\]于是\[(a,b,c)=(1,0,3),(0,2,2),\]对应的映射 $f$ 的个数为\[ 2\left[\dbinom{4}{1~0~3}+\dbinom{4}{0~2~2}\right]=20. \] 如果递减发生在 $f(n)-f(n+1)$($n=1,2,3,4$),注意到\[|(n+1)-(n-1)|\leqslant |f(n+1)-f(n-1)|\leqslant |f(n+1)-f(n-1)|\implies f(n+1)-f(n-1)\geqslant 2,\]于是 $f(n)-f(n+1)=1$,且\[f(n+2)-f(n+1)=f(n)-f(n-1)=3,\]因此 $f(n-1),f(n+2)$ 的值均决定于 $f(n)$ 的值,且\[f(n+2)-f(n-1)=5,\]所以还需要确定其他的 $3$ 个值,且递增总和为 $7$,只可能为 $1+3+3$ 或 $2+2+3$,进而对应的映射 $f$ 为\[2(3+3)=24.\]

综上所述,所求不同的映射总数为 $141+20+24=185$.

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

发表评论