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

Solución. En primer lugar, el hecho de saber que $g(n)$ se define sobre los números pares e impares nos hace pensar en utilizar la base $2$ para expresar la función. Calculando unos cuantos términos $g(n)$ y expresando $n$ en base $2$, parece que $g(n)$ es la suma de las cifras de $n$ en base $2$ y esto será lo que probemos por inducción completa.

Está claro que, para $n=1$ ó $n=2$, $g(1)=g(2)=1$, con lo cual se cumple el caso base. Dado $n\in\mathbb{N}$, supongamos ahora que $g(j)$ es la suma de los dígitos de $j$ para $1\leq j\lt n$ y probémoslo para $n$. Tendremos que distinguir casos dependiendo de si $n$ es par o impar:

• Si $n$ es par, entonces $n=2j$ para algún $j$, luego $g(n)=g(2j)=g(j)$. Ahora bien, los dígitos de $n$ en base $2$ son los de $j$ a los que se ha añadido un cero al final, luego $g(n)$ también es la suma de los dígitos de $n$ en base $2$.
• Si $n$ es impar, entonces $n=2j+1$ para algún $j$, luego $g(n)=g(2j+1)=g(2j)+1=g(j)+1$. Como los dígitos de $n$ en base $2$ son los de $j$ a los que se ha añadido un uno al final, tendremos que $g(n)$ es la suma de los dígitos de $n$ en base $2$.

Visto esto, el problema se reduce a saber cuál es el número $n\leq 2002$ con mayor suma de dígitos en base $2$ o, equivalentemente, con mayor número de unos en base $2$. El primer número que tiene $k$ unos en base $2$ es $2^k-1$. Como $2^{10}-1=1023\lt 2002$ y $2^{11}-1=2047\gt 2002$, deducimos que $M=10$.

Falta por ver cuántos números $n\leq 2002$ tienen exactamente $10$ unos en base $2$. No obstante, como dichos números tienen a lo sumo $11$ cifras, los posibles candidatos son los que tienen exactamente un cero, que son los de la forma $2^{11}-2^{i}-1$ para $0\leq i\leq 10$.

• Para $i\leq 5$ tenemos que $2^{11}-2^{i}-1\geq 2^{11}-2^5-1=2015$.
• Para $i\geq 6$ tenemos que $2^{11}-2^{i}-1\leq 2^{11}-2^6-1=1983$.

Por tanto, los números buscados son los que se obtienen para $6\leq i\leq 10$ y, deducimos que hay exactamente cinco números que alcanzan el máximo.