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

Solución. Que el número $n$ sea sensato equivale a que \[n=a(1+r+r^2+\ldots+r^k)\] para ciertos $a,r\in\mathbb{N}$ tales que $1\lt r\lt n-1$ y $1\leq a\leq r-1$. El caso de $1994=2\cdot 997$ es obvio ya que basta tomar $a=2$, $r=996$ y $k=1$, lo que nos da la representación $1994=22_{(996)}$.

Como $1993$ es primo, no vale el truco anterior y tenemos que necesariamente $a=1$. Por tanto, $1993$ será sensato cuando podamos encontrar $r,k\geq 2$ tales que \[1993=1+r+\ldots+r^k.\] Esta ecuación nos dice además que $r$ debe ser un divisor de $1992=2^3\cdot 3\cdot 81$. No obstante, $r$ no puede ser múltiplo de $81$ ya que $81^2\gt 1993$, lo que nos deja sólo las posibilidades $r\in\{2,3,4,6,8,12,24\}$. En realidad, se pueden probar una a una sin perder demasiado tiempo, pero una opción sin tanto cálculo es observar que \[1993=1+r+\ldots+r^k=\frac{r^{k+1}-1}{r-1}\ \Leftrightarrow\ 1+1993(r-1)=r^{k+1},\] luego sólo tenemos que calcular $1+1993(r-1)$ y ver si es potencia de $r$ o no:

• Para $r=2$, tenemos que $1+1993(r-1)=1994=2\cdot 997$ no es potencia de $2$.
• Para $r=3$, tenemos que $1+1993(r-1)=3987=9\cdot 443$ no es potencia de $3$.
• Para $r=4$, tenemos que $1+1993(r-1)=5980$ es múltiplo de $5$ y no es potencia de $4$.
• Para $r=6$, tenemos que $1+1993(r-1)=9966$ es múltiplo de $11$ y no es potencia de $6$.
• Para $r=8$, tenemos que $1+1993(r-1)=13952=2^7\cdot 109$ no es potencia de $8$
• Para $r=12$, tenemos que $1+1993(r-1)=21924$ es múltiplo de $7$ y no es potencia de $12$.
• Para $r=24$, tenemos que $1+1993(r-1)=45840$ es múltiplo de $5$ y no es potencia de $24$.

Concluimos que $1993$ no es sensato.

Solución. Si $n$ es impar, podemos tocar todas las lámparas de la primera fila (o de culquier fila o columna) y todas quedan encendidas. En este caso, $n$ es realmente el mínimo número de toques ya que, si sólo tocáramos $n-1$ lámparas o menos, entonces habría una fila y una columna en la que no tocaríamos ninguna lámpara. La casilla intersección de esta fila y columna quedaría apagada.

Si $n$ es par, entonces nuestro objetivo se cumplirá si tocamos las $n^2$ lámparas ya que a cada lámpara le afectan $2n-1$ cambios de estado (en realidad, esto también funciona para $n$ impar pero no es óptimo, como acabamos de ver). Veamos que, si no tocamos todas las lámparas, entonces habrá alguna que quede apagada, lo que probará que $n^2$ es óptimo en este caso (observemos que no tiene sentido tocar una misma lámpara dos veces).

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.