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

Solución. Vamos a probar que si expresamos $n$ en base $2$ con solo ceros y unos, el número $f(n)$ es el que tiene esa misma representación en base $3$. Eso hace que el conjunto de valores que toma $f$ son los números que se escriben solamente con ceros y unos en base $3$, es decir, los números que son suma de potencias distintas de $3$.

Vamos a proceder por inducción completa sobre $n$. El caso base $n=1$ está claro ya que $f(1)=1$ y $1$ se expresa igual en ambas bases. Supongamos entonces que el resultado es cierto hasta cierto valor $n$ y veamos lo que ocurre con $n+1$. Podemos escribir \[n+1=2^ka_k+\ldots+4a_2+2a_1+a_0,\] siendo $a_k\ldots a_2a_1a_0$ los dígitos de $n+1$ en base $2$. Distinguimos dos casos según el valor de $a_0$:

• Si $a_0=0$, entonces podemos escribir \begin{align*} f(n+1)&=f(2(2^{k-1}a_k+\ldots+2a_2+a_1))=3f(2^{k-1}a_k+\ldots+2a_2+a_1)\\ &=3f(3^{k-1}a_k+\ldots+3a_2+a_1)=3^ka_k+\ldots+9a_2+3a_1, \end{align*} donde hemos usado que $2^{k-1}a_k+\ldots+2a_2+a_1=\frac{n-1}{2}\lt n$ y la hipótesis de inducción. Por tanto, tenemos que $f(n+1)$ es el número que tiene los dígitos $a_k\ldots a_2a_1a_0$ en base $3$.
• De forma similar, si $a_0=1$, entonces \begin{align*} f(n+1)&=f(2(2^{k-1}a_k+\ldots+2a_2+a_1)+1)=f(2(2^{k-1}a_k+\ldots+2a_2+a_1))+1\\ &=f(2^{k}a_k+\ldots+4a_2+2a_1)+1=3^{k}a_k+\ldots+9a_2+3a_1+1, \end{align*} vuelve a ser el número con dígitos $a_k\ldots a_2a_1a_0$ en base $3$. Aquí hemos aplicado la hipótesis de inducción a $n=2^{k}a_k+\ldots+4a_2+2a_1$.