Задача М1132‍‍

Ответ: 92.

Докажем индукцией по числу $k$‍‍ знаков в двоичной записи $\overline{a_1a_2\ldots a_{k-1}a_k\vphantom0}$‍‍ ($a_1=1$‍)‍ числа $m$‍,‍ что $$ f(m)=\overline{a_ka_{k-1}\ldots a_2a_1\vphantom0}.\tag{*} $$ При $k=1$‍‍ имеем $f(1)=1$‍;‍ при $k=2$‍‍ имеем $$ \begin{gather*} f(\overline{10})=f(2)=f(1)=1=\overline{01},\\ f(\overline{11})=f(3)=3=\overline{11}. \end{gather*} $$ Докажем теперь наше утверждение для $k$‍‍-значного ($k\gt2$‍)‍ в двоичной системе числа $m$‍,‍ считая, что оно верно для всех чисел с меньшим числом знаков. Рассмотрим три возможных случая.

1. $m$‍‍ чётно: $m=2n=\overline{a_1\ldots a_{k-1}0}$‍.‍ Тогда $n=\overline{a_1\ldots a_{k-1}\vphantom0}$‍‍ и $$ f(m)=f(n)=\overline{a_{k-1}\ldots a_1\vphantom0}=\overline{0a_{k-1}\ldots a_1}. $$
2. $m=4n+1=\overline{a_1\ldots a_{k-2}01}$‍.‍ Тогда $n=\overline{a_1\ldots a_{k-2}\vphantom0}$‍‍ $2n+1=\overline{a_1\ldots a_{k-2}1}$‍‍ и $$ \begin{gather*} f(m)=2f(2n+1)-f(n)=f(2n+1)+(f(2n+1)-f(n))=\\ =\overline{1a_{k-2}\ldots a_1}+(\overline{1a_{k-2}\ldots a_1}-\overline{a_{k-2}\ldots a_1\vphantom1})=\overline{10a_{k-2}\ldots a_1}. \end{gather*} $$
3. $m=4n+3=\overline{a_1\ldots a_{k-2}11}$‍.‍ Тогда $n=\overline{a_1\ldots a_{k-2}\vphantom0}$‍‍ и $$ \begin{gather*} f(m)=3f(2n+1)-2f(n)=f(2n+1)+2(f(2n+1)-f(n))=\\ =\overline{1a_{k-2}\ldots a_1}+2(\overline{1a_{k-2}\ldots a_1}-\overline{a_{k-2}\ldots a_1}\vphantom0)=\overline{11a_{k-2}\ldots a_1}. \end{gather*} $$

Во всех случаях формула (*) верна; тем самым она доказана для всех $m$‍.‍

Из формулы (*) следует, что $f(m)=m$‍‍ для чисел $m$‍,‍ двоичная запись которых симметрична. Чтобы получить все такие числа с $2k-1$‍‍ или $2k$‍‍ двоичными знаками, надо на первое место записи поставить $a_1=1$‍,‍ следующие $k-1$‍‍ мест $a_2$‍,‍ $\ldots$‍,‍ $a_k$‍‍ заполнить произвольно, а оставшиеся места — симметрично первым $k$‍.‍ Это даёт по $2^{k-1}$‍‍ чисел. Поскольку $2^{10}\lt1988\lt2^{11}$‍‍ и имеется только два 11-значных «двоично-симметричных» числа, больших $1988=\overline{11111000100}$‍,‍ — это $\overline{11111011111}$‍‍ и $\overline{11111111111}$‍,‍ искомое число равно $2(1+2+2^2+2^3+2^4)+2^5-2=92$‍.‍