每日一题[1543]映射计数

已知正整数 $n$ 都可以唯一表示为\[n=a_0+a_1\cdot 9+a_2\cdot 9^2+\cdots +a_m\cdot 9^m\]的形式,其中 $m$ 为非负整数,$a_j\in\{0,1,\cdots,8\}$($j=0,1,\cdots,m-1$),$ a_m\in\{1,\cdots,8\} $.试求使得上述等式中的数列 $ a_0,a_1,a_2,\cdots,a_m $ 严格单调递增或严格单调递减的所有正整数 $ n$(包含对应的数列只有一项的情形)的和.

答案       $984374748$.

解析       记 $p(n)$ 为正整数 $n$ 对应的数列 $a_0,a_1,a_2,\cdots,a_m$,设 $A$ 和 $B$ 分别表示使 $p(n)$ 单调递增和单调递减的正整数 $n$ 构成的集合,用 $S(M)$ 表示集合 $M$ 中的所有数之和,并记\[n=\overline{a_ma_{m-1}\cdots a_1 a_0}.\]接下来尝试获得 $S(A)$ 与 $S(B)$ 的联系.

第一个方程       把集合 $A$ 做如下分划:\[\begin{split} A_0&=\{n\in A\mid a_0=0\},\\ A_1&=\{n\in A\mid a_0\ne 0\},\end{split}\]则 $f:n\mapsto 9n$ 是 $A_1$ 到 $A_0$ 的一一映射,于是\[S(A_0)=9S(A_1)\implies S(A)=10S(A_1).\]又\[g:\overline{a_m a_{m-1}\cdots a_1a_0}\mapsto \overline{(9-a_m)(9-a_{m-1})\cdots(9-a_1)(9-a_0)}\]是 $B$ 到 $A_1$ 的一一映射,且\[\overline{a_m a_{m-1}\cdots a_1a_0}+\overline{(9-a_m)(9-a_{m-1})\cdots(9-a_1)(9-a_0)}=\dfrac 98\left(9^{m+1}-1\right),\]于是\[\begin{split} S(B)+S(A_1)&=\sum_{m=0}^7\left(\mathop{\rm C}\nolimits_8^{m+1}\cdot \dfrac 98\left(9^{m+1}-1\right)\right)\\ &=\dfrac 98\sum_{k=0}^8\mathop{\rm C}\nolimits_8^k9^k-\dfrac 98\sum_{k=0}^8\mathop{\rm C}\nolimits_8^k\\ &=\dfrac 98\left(10^8-2^8\right).\end{split}\]这样我们就得到了方程\[S(B)+\dfrac1{10}S(A)=\dfrac 98\left(10^8-2^8\right).\]

第二个方程       把集合 $A$ 做如下分划:\[\begin{split} A_2&=\{n\in A\mid a_m=8\},\\ A_3&=\{n\in A\mid a_m\ne 8\},\end{split}\]则\[h:\overline{a_m a_{m-1}\cdots a_1a_0}\mapsto \overline{(8-a_m)(8-a_{m-1})\cdots(8-a_1)(8-a_0)}\]是 $B$ 到 $A_3$ 的一一映射,且\[\overline{a_m a_{m-1}\cdots a_1a_0}+\overline{(8-a_m)(8-a_{m-1})\cdots(8-a_1)(8-a_0)}=9^{m+1}-1,\]所以\[\begin{split} S(B)+S(A_3)&=\sum_{m=0}^7\mathop{\rm C}\nolimits_8^{m+1}\left(9^{m+1}-1\right)\\ &=\sum_{k=0}^8\mathop{\rm C}\nolimits_8^k9^k-\sum_{k=0}^8\mathop{\rm C}\nolimits_8^k\\ &=10^8-2^8.\end{split}\] 同时考虑集合 $A_2\backslash\{8\}$ 到 $B$ 的一一映射\[h':\overline{8a_m a_{m-1}\cdots a_1a_0}\mapsto \overline{(8-a_m)(8-a_{m-1})\cdots(8-a_1)(8-a_0)},\]且\[\overline{8a_m a_{m-1}\cdots a_1a_0}+ \overline{(8-a_m)(8-a_{m-1})\cdots(8-a_1)(8-a_0)}=9^{m+2}-1,\]所以\[\begin{split} S(B)+S(A_2)&=8+\sum_{m=0}^7\mathop{\rm C}\nolimits_8^{m+1}\left(9^{m+2}-1\right)\\ &=8+9\sum_{k=1}^8\mathop{\rm C}\nolimits_8^k9^k-\sum_{k=1}^8\mathop{\rm C}\nolimits_8^k\\ &=9\cdot 10^8-2^8.\end{split}\]这样就得到了方程\[2S(B)+S(A)=10^9-2^9.\]

综合以上,有\[\begin{cases} S(B)+\dfrac1{10}S(A)=\dfrac 98\left(10^8-2^8\right),\\ 2S(B)+S(A)=10^9-2^9,\end{cases}\iff \begin{cases} S(A)=968750080,\\ S(B)=15624704,\end{cases}\]于是所求正整数的和为\[S(A)+S(B)-(1+2+\cdots+8)=984374748.\]

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

发表评论