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

Solución. Las primeras $2^{12}-2=4094$ sumas las emplearemos en obtener los números desde el $2$ hasta el $2^{12}-1$ sin más que sumar $1$ consigo mismo repetidamente. En base $2$ esto nos da todos los números de $11$ cifras y también el $2^{12}$, que es un uno seguido de once ceros. Veamos cómo usar esto para hallar cualquier número $n$ de $999999$ cifras en base $2$, cifras que se pueden agrupar en $90909$ grupos de once dígitos consecutivos formando números de once cifras $S_1,S_2,\ldots,S_{90909}$, siendo $S_1$ las once cifras más significativas

Como $S_1\leq 4095$, este número se encuentra entre los calculados. Ahora lo sumamos consigo mismo para obtener $2S_1$ y este resultado lo sumamos consigo mismo para obtener $4S_1$ y así sucesivamente hasta obtener $2^{11}S_1$, que es el número $S_1$ seguido de $11$ ceros. Ahora sumamos al resultado $S_2$ y ya tenemos el número $2^{11}S_1+S_2$, que contiene las veintidós cifras más significativas de $n$. Lo sumamos consigo mismo de forma que en otros once pasos obtenemos $2^{22}S_1+2^{11}S_2$ y le sumamos $S_3$. Podemos repetir este proceso para conseguir todas las cifras de $n$. Por cada grupo de once cifras que añadimos, hemos necesitado $12$ sumas (once para multiplicar por $2^{11}$ y una para añadir once nuevos dígitos), lo que hace un total de $4095+12\cdot 90908=1094991\lt 1100000$.

Queda el caso de que $n=2^{1000000}$, pero este número se obtiene con solo $1000000$ sumas sin más que sumar $1$ consigo mismo y luego $2$ consigo mismo, luego $4$ consigo mismo, y así sucesivamente.

Nota. Esta solución funciona haciendo grupos de $11$ (como hemos hecho), de $12$ (se obtiene un máximo de $1091520$ sumas) o $13$ dígitos ($1093291$ sumas). Con grupos de más de $13$ dígitos o de menos de $11$, necesitaríamos en general más de $1100000$ sumas mediante este método.