Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Vamos a comenzar probando que, si $0\leq e_1\lt e_2\lt\ldots\lt e_k$ son enteros, entonces se cumple que \[f(2^{e_1}+2^{e_2}+\ldots+2^{e_k})=(-1)^{e_1}+(-1)^{e_2}+\ldots+(-1)^{e_k}.\] Como todo entero positivo se expresa de forma única como suma de potencias distintas de $2$ (pensemos en el número escrito en el sistema binario), lo anterior nos determina completamente a $f$. Observamos también que $0$ es par, luego $f(0)=0$. Para ver cómo se nos puede ocurrir la fórmula anterior, véase la nota más abajo.

Vamos a probar la fórmula anterior por inducción sobre el número de sumandos $k$. Si $k=1$, entonces $f(2^{e_1})=(-1)^{e_1}f(1)$ aplicando reiteradamente la definición de $f(n)$ para $n$ par. Además, se tiene que $f(1)=f(0)+1=1$, lo que prueba que $f(2^{e_1})=(-1)^{e_1}$, como queríamos. Supongamos entonces que la igualdad es cierta para $k-1$ sumandos y demostrémosla para $k$ sumandos. Suponiendo que $e_1$ es el exponente más pequeño (como arriba), tenemos que \begin{align*} f(2^{e_1}+2^{e_2}+\ldots+2^{e_k})&=(-1)^{e_1}f(1+2^{e_2-e_1}+\ldots+2^{e_k-e_1})\\ &=(-1)^{e_1}(1+f(2^{e_2-e_1}+\ldots+2^{e_k-e_1}))\\ &\stackrel{(\star)}{=}(-1)^{e_1}(1+(-1)^{e_2-e_1}+\ldots+(-1)^{e_k-e_1})\\ &=(-1)^{e_1}+(-1)^{e_2}+\ldots+(-1)^{e_k}, \end{align*} donde en el la igualdad $(\star)$ se ha usado la hipótesis de inducción.

Teniendo en cuenta lo anterior y que $2\equiv -1\ (\text{mod }3)$ tenemos claramente el apartado (a). Si expresamos $n=2^{e_1}+\ldots+2^{e_k}$ como suma de potencias distintas de $2$, entonces \[f(n)=(-1)^{e_1}+\ldots+(-1)^{e_k}\equiv 2^{e_1}+\ldots+2^{e_k}=n\ (\text{mod }3),\] luego $f(n)$ es múltiplo de $3$ si y sólo si lo es $n$.

En cuanto al apartado (b), cada potencia de $2$ de exponente par suma una unidad y cada potencia de exponente impar resta una unidad, luego el menor $n$ tal que $f(n)=2017$ será la suma de las primeras $2017$ potencias de $2$ pares, es decir, la solución que buscamos es \[n=2^0+2^2+2^4+\ldots+2^{2\cdot 2016}=1+4+4^2+\ldots+4^{2016}=\frac{4^{2017}-1}{3},\] donde hemos usado la fórmula para la suma de los términos de una progresión geométrica.

Nota. Veamos cómo justificar la idea feliz con la que empieza la solución. Supongamos que el número $n$ está escrito en el sistema binario, únicamente con ceros y unos. Hagamos algunas observaciones previas:

• Por un lado, $n$ es par cuando su último dígito es $0$, en cuyo caso $\frac{n}{2}$ consiste en eliminar ese cero. Por lo tanto, si $n$ termina en $r$ ceros, tendremos que es múltiplo de $2^r$ y $f(n)=(-1)^rf(\frac{n}{2^r})$, donde ahora hay que calcular $f$ sobre el número $\frac{n}{2^r}$, que consiste en eliminar esos $r$ ceros de la expresión de $n$.
• Por otro lado, $n$ es impar cuando su último dígito es $1$ y ahora $n-1$ consiste en cambiar ese $1$ por un $0$. Por tanto, $f(n)=f(n-1)+1$ reduce el problema a calcular $f$ sobre un número que termina en ceros y aplicar el caso previo.
• Los pasos anteriores reducen progresivamente el número de dígitos de $n$ hasta llegar a un punto en que es necesario calcular $f(0)$. Por la propia ecuación, como $0$ es par, tendremos que $f(0)=-f(0)$, luego $f(0)=0$ necesariamente.

De esta forma, no es difícil convencerse de que para calcular $f(n)$, sólo hay que leer $f$ en binario de derecha a izquierda, sumando $1$ por cada $1$ que vayamos encontrando y multiplicando por $(-1)^{r+1}$ siempre que nos encontremos $r$ ceros seguidos. Esto se resume en que cada $1$ que aparece introduce realmente un sumando $(-1)^{s+1}$, siendo $s$ la posición en la que aparece y podemos intuir así que cada sumando $2^s$ se transforma en un sumando $(-1)^s$.