设 $\mathbb{N}^{\ast}$ 为正整数集，在 $\mathbb{N}^{\ast}$ 上定义函数 $f$ 如下：
（1）$f(1)=1,f(3)=3$；
（2）对 $n\in\mathbb{N}^+$，有
$\begin{aligned}
& f(2n)=f(n), \\
& f(4n+1)=2f(2n+1)-f(n), \\
& f(4n+3)=3f(2n+1)-2f(n)
\end{aligned}$
问：有多少个 $n\in\mathbb{N}^{\ast}$，且 $ n\leqslant 1988 $，使得 $ f(n)=n$？（英国）
（1）$f(1)=1,f(3)=3$；
（2）对 $n\in\mathbb{N}^+$，有
$\begin{aligned}
& f(2n)=f(n), \\
& f(4n+1)=2f(2n+1)-f(n), \\
& f(4n+3)=3f(2n+1)-2f(n)
\end{aligned}$
问：有多少个 $n\in\mathbb{N}^{\ast}$，且 $ n\leqslant 1988 $，使得 $ f(n)=n$？（英国）
【难度】
【出处】
1988年第29届IMO试题
【标注】
【答案】
略
【解析】
如果能确定 $f$ 的表达式，问题便迎刃而解了．
设 $n$ 的二进制表示为 $(a_sa_{s-1}\cdots a_1)$，我们将证明：
$f(n)=(a_1a_2\cdots a_s)_2$ ①
当 $n=1,2,3$ 时，上式显然成立．
由于 $f(2n)=f(n)$，所以只需考虑 $n$ 是奇数的情况．设 ① 式在 $<n$ 时成立，现在考虑 $f(n)$．
（1）当 $n=4m+1$ 时，设 $4m+1=(a_ka_{k-1}\cdots a_0)_2$，其中 $a_0=1,a_1=0$．于是 $4m=(a_ka_{k-1}\cdots a_10)_2$，由此可得
$m=(a_ka_{k-1}\cdots a_2)_2,2m+1=(a_ka_{k-1}\cdots a_21)_2$
由归纳即设可知
$f(2m+1)=(1a_2a_3\cdots a_k)_2$
$f(m)=(a_2a_3\cdots a_k)_2$
所以
$\begin{aligned}
f(4m+1)&=2f(2m+1)-f(m)\\
&=(1a_2a_3\cdots a_k0)_2-(a_2a_3\cdots a_k)_2\\
&=2^k+\sum_{j=2}^ka_j\cdot 2^{k+1-j}-sum_{j=2}^ka_j\cdot 2^{k-j}\\
&=2^k+\sum_{j=2}^ka_j\cdot 2^{k-j}\\
&=\sum_{j=0}^ka_j\cdot 2^{k-j}\\
&=(a_0a_1\cdots a_k)_2
\end{aligned}$
结论成立．
（2）当 $n=4m+3$ 时，仍设 $4m+3=(a_ka_{k-1}\cdots a_0)_2$，其中 $a_0=a_1=1$，因此 $4m=(a_ka_{k-1}\cdots a_200)_2,m=(a_ka_{k-1}\cdots a_2)_2,2m+1=(a_ka_{k-1}\cdots a_21)_2$．
由归纳假设及题设知
$\begin{aligned}
f(4m+3)&=3f(2m+1)-2f(m)\\
&=3(1a_2a_3\cdots a_k)_2-2(a_2a_3\cdots a_k)_2\\
&=(1a_2\cdots a_k0)_2+(1a_2\cdots a_k)_2-(a_2a_3\cdots a_k0)_2\\
&=2^k+(1a_2\cdots a_k)_2\\
&=(11a_2\cdots a_k)_2\\
&=(a_0a_1a_2\cdots a_k)_2
\end{aligned}$
于是结论得证．
由于 $f(n)=n\Leftrightarrow (a_1a_2\cdots a_k)_2=(a_ka_{k-1}\cdots a_1)_2$，其中 $n=(a_ka_{k-1}\cdots a_1)_2$，即满足 $f(n)=n$ 的二进制数 $n$ 是"对称"的．因此，若 $n$ 的二进制中有 $2m$ 位数码，则它完全被前 $m$ 位数码所决定．由于第一位是 $1$，后面连续的 $m-1$ 位可在 $0,1$ 中任取，故具有 $2m$ 位数码的对称二进制数有 $2^{m-1}$ 个．同样地，具有 $2m-1$ 位数码的对称二进制数也有 $2^{m-1}$ 个．
因为 $2^{10}<1988<2^{11}$，所以在小于 $2048$ 的正整数中，满足条件 $f(n)=n$ 的正整数 $n$ 一共有 $1+1+2+2+4+4+8+8+16+16+32=94$（个）．
又由于 $1988=(11111000100)_2$，故超过 $1988$ 的对称数只有两个，它们是 $(11111011111)_2,(11111111111)_2$，所以有 $92$ 个不超过 $1988$ 的正整数 $n$，使得 $f(n)=n$．
设 $n$ 的二进制表示为 $(a_sa_{s-1}\cdots a_1)$，我们将证明：
$f(n)=(a_1a_2\cdots a_s)_2$ ①
当 $n=1,2,3$ 时，上式显然成立．
由于 $f(2n)=f(n)$，所以只需考虑 $n$ 是奇数的情况．设 ① 式在 $<n$ 时成立，现在考虑 $f(n)$．
（1）当 $n=4m+1$ 时，设 $4m+1=(a_ka_{k-1}\cdots a_0)_2$，其中 $a_0=1,a_1=0$．于是 $4m=(a_ka_{k-1}\cdots a_10)_2$，由此可得
$m=(a_ka_{k-1}\cdots a_2)_2,2m+1=(a_ka_{k-1}\cdots a_21)_2$
由归纳即设可知
$f(2m+1)=(1a_2a_3\cdots a_k)_2$
$f(m)=(a_2a_3\cdots a_k)_2$
所以
$\begin{aligned}
f(4m+1)&=2f(2m+1)-f(m)\\
&=(1a_2a_3\cdots a_k0)_2-(a_2a_3\cdots a_k)_2\\
&=2^k+\sum_{j=2}^ka_j\cdot 2^{k+1-j}-sum_{j=2}^ka_j\cdot 2^{k-j}\\
&=2^k+\sum_{j=2}^ka_j\cdot 2^{k-j}\\
&=\sum_{j=0}^ka_j\cdot 2^{k-j}\\
&=(a_0a_1\cdots a_k)_2
\end{aligned}$
结论成立．
（2）当 $n=4m+3$ 时，仍设 $4m+3=(a_ka_{k-1}\cdots a_0)_2$，其中 $a_0=a_1=1$，因此 $4m=(a_ka_{k-1}\cdots a_200)_2,m=(a_ka_{k-1}\cdots a_2)_2,2m+1=(a_ka_{k-1}\cdots a_21)_2$．
由归纳假设及题设知
$\begin{aligned}
f(4m+3)&=3f(2m+1)-2f(m)\\
&=3(1a_2a_3\cdots a_k)_2-2(a_2a_3\cdots a_k)_2\\
&=(1a_2\cdots a_k0)_2+(1a_2\cdots a_k)_2-(a_2a_3\cdots a_k0)_2\\
&=2^k+(1a_2\cdots a_k)_2\\
&=(11a_2\cdots a_k)_2\\
&=(a_0a_1a_2\cdots a_k)_2
\end{aligned}$
于是结论得证．
由于 $f(n)=n\Leftrightarrow (a_1a_2\cdots a_k)_2=(a_ka_{k-1}\cdots a_1)_2$，其中 $n=(a_ka_{k-1}\cdots a_1)_2$，即满足 $f(n)=n$ 的二进制数 $n$ 是"对称"的．因此，若 $n$ 的二进制中有 $2m$ 位数码，则它完全被前 $m$ 位数码所决定．由于第一位是 $1$，后面连续的 $m-1$ 位可在 $0,1$ 中任取，故具有 $2m$ 位数码的对称二进制数有 $2^{m-1}$ 个．同样地，具有 $2m-1$ 位数码的对称二进制数也有 $2^{m-1}$ 个．
因为 $2^{10}<1988<2^{11}$，所以在小于 $2048$ 的正整数中，满足条件 $f(n)=n$ 的正整数 $n$ 一共有 $1+1+2+2+4+4+8+8+16+16+32=94$（个）．
又由于 $1988=(11111000100)_2$，故超过 $1988$ 的对称数只有两个，它们是 $(11111011111)_2,(11111111111)_2$，所以有 $92$ 个不超过 $1988$ 的正整数 $n$，使得 $f(n)=n$．
答案
解析
备注
