CSP-S 2023 第一轮 第14题：十六进制反复求数位和

题目

若 $n=\sum_{i=0}^k {16^i\cdot x_i}$，定义 $f(n)=\sum_{i=0}^k {x_i}$，其中 $x_i\in\{0,1,\cdots,15\}$。对于给定自然数 $n_0$，存在序列 $n_0,n_1,n_2,\cdots,n_m$，其中对于 $1 \le i \le m$ 都有 $n_i=f(n_{i-1})$，且 $n_m=n_{m-1}$，称 $n_m$ 为 $n_0$ 关于 $f$ 的不动点。问在 $100_{16}$ 到 $1A0_{16}$ 中，关于 $f$ 的不动点为 $9$ 的自然数个数为（）。

选项

• A. $10$
• B. $11$
• C. $12$
• D. $13$

答案

B

题解

答案是 B．\(11\)。

关键是：十六进制数与它的数位和模 \(15\) 同余。因为 \(16\equiv1\pmod{15}\)，所以 \[ n=\sum 16^ix_i\equiv\sum x_i=f(n)\pmod{15}. \] 因此，反复求数位和，模 \(15\) 的余数始终不变。

当 \(n\ge16\) 时，\(f(n)<n\)；当 \(0\le n\le15\) 时，\(f(n)=n\)。所以最终一定停在 \(0\) 到 \(15\) 之间，其中只有 \(9\) 模 \(15\) 余 \(9\)。于是 \[ \boxed{\text{不动点为 }9\iff n\equiv9\pmod{15}}. \]

把区间端点转为十进制： \[ 100_{16}=256,\qquad 1A0_{16}=416. \] 区间内模 \(15\) 余 \(9\) 的数为 \[ 264,\ 279,\ 294,\ \ldots,\ 414, \] 共有 \[ \frac{414-264}{15}+1=\boxed{11} \] 个。