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

Solución. Todo número natural $n$ se puede expresar de forma única como suma de potencias distintas de $2$, es decir, existen enteros $0\leq a_1\lt a_2\lt\ldots\lt a_r$ únicos tales que \[n=2^{a_1}+2^{a_2}+\ldots+2^{a_r}\] (esto no es más que la representación de $n$ en base $2$). Es inmediato ver, por inducción sobre $r$, que $f(n)=r$. En efecto, si $r=1$, tenemos que $n=2^{a_1}$ y $f(n)=f(2^{a_1})=1$ por la primera propiedad del enunciado (notemos que $2^{a_1}=1$ si $a_1=0$). Supuesto cierto para $r-1$ sumandos, para $r$ sumandos tenemos que \[f(2^{a_1}+2^{a_2}+\ldots+2^{a_r})=f(2^{a_1}+2^{a_2}+\ldots+2^{a_{r-1}})+1=(r-1)+1=r,\] puesto que \[2^{a_1}+2^{a_2}+\ldots+2^{a_{r-1}}\leq 1+2+2^2+\ldots+2^{a_r-1}=2^{a_r}-1\lt 2^{a_r}\] y puede aplicarse la segunda propiedad del enunciado.

En definitiva, hemos probado que $f(n)$ es la suma de los dígitos de $n$ en base $2$. Dado $k\in\mathbb{N}$, está claro entonces que el menor número con $f(n)=k$ es $n=2^k-1$ (que tiene $k$ dígitos en base $2$, todos ellos iguales a $1$). Como $2^{10}\lt 2001\lt 2^{11}-1$, deducimos que el máximo de $f(n)$ cuando $n\leq 2001$ es $10$. También deducimos que el menor natural $n$ tal que $f(n)=2001$ es $2^{2001}-1$.