Sea [math]S_n el conjunto de todos los números de [math]n dígitos (incluye a los que comienzan con [math]0). Se dice que cuatro números de [math]S_n forman una cuaterna especial si los números coinciden en todas las posiciones excepto una, en la cual tienen cuatro dígitos consecutivos. Por ejemplo, [math]\{24438, 24448, 24458, 24468\} y [math]\{06921, 07921, 08921, 09921\} son cuaternas especiales de [math]5 dígitos.
Determinar, para cada [math]n, el máximo número de cuaternas especiales que se pueden formar de modo que ningún número figure en más de una cuaterna.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Para $n=1$ es claro que $\{0,1,2,3\}$, $\{4,5,6,7\}$ son cuaternas especiales por lo que tenemos un ejemplo.
Para $n>1$:
- Tomamos para todo número $A$ de $n-1$ dígitos las cuaternas $\{A,10^{n-1}+A,2\cdot 10^{n-1}+A,3\cdot 10^{n-1}+A\}$ y $\{4\cdot 10^{n-1}+A,5\cdot 10^{n-1}+A,5\cdot 10^{n-1}+A,7\cdot 10^{n-1}+A\}$, de modo que el primer dígito sea el diferente. Acá hay $2\cdot 10^{n-1}$ cuaternas, dos por cada $A$.
- Tomamos todas las cuaternas especiales con $n-1$ dígitos y a cada uno de sus elementos le agregamos como primer dígito un $8$ y un $9$, formando dos cuaternas distintas. Entonces, si suponemos que con $n-1$ dígitos hay $f(n-1)=2,5\cdot 10^{n-2}-2^{n-3}$ cuaternas especiales, acá tenemos $2f(n-1)=0,5\cdot 10^{n-1}-2^{n-2}$ cuaternas.
En total, hay $2\cdot 10^{n-1}+0,5\cdot 10^{n-1}-2^{n-2}$ cuaternas especiales que no se solapan, como queríamos.
Pintamos de rojo todos los números de $S_n$ que cumplen las siguientes dos condiciones:
i. El número tiene una cantidad impar de dígitos congruentes a $1$ o $3$ módulo $4$. ii. El número tiene una cantidad impar de dígitos congruentes a $2$ o $3$ módulo $4$.
Primero, fijémonos que si tenemos cuatro dígitos consecutivos, hay uno de cada resto, por lo que uno de ellos no cumple ni i. ni ii. (tiene resto $0$), uno cumple sólo i. (tiene resto $1$), uno cumple sólo ii. (tiene resto $2$) y el último cumple i. y ii. (tiene resto $3$).
Entonces, si tomamos una cuaterna especial, no importa cuales sean los dígitos no distintos, siempre uno de sus números va a ser rojo. Por ejemplo, si entre los $n-1$ dígitos no distintos hay una cantidad par que están en el primer conjunto y una cantidad impar que están en el segundo, entonces cuando el dígito distinto esté en el primero pero no en el segundo (ya demostramos que alguno había), entonces el número cumplirá ambas condiciones y por ende será rojo. De manera similar se resuelven los otros casos.
Segundo, vamos a contar la cantidad de números que cumplen ambas condiciones:
Notemos que si tomamos los últimos $n-1$ dígitos de cada número rojo, entonces el primer dígito sólo tiene una posibilidad módulo $4$ (el razonamiento es similar al que usamos antes). Explicitamente, si el número formado por los $n-1$ dígitos finales cumple i. y ii., el primer dígito sólo puede ser $0$, $4$ u $8$; si cumple sólo ii., entonces el primero sólo puede ser $1$, $5$ o $9$; si cumple sólo i., sólo puede ser $2$ o $6$, y si no cumple ninguna, sólo puede ser $3$ o $7$. Es decir, sean $a(k)$, $b(k)$, $c(k)$ y $d(k)$ la cantidad de números de $k$ dígitos que cumplen ambas, sólo i., sólo ii. y ninguna, respectivamente. Entonces,
$$a(n)=3a(n-1)+3c(n-1)+2b(n-1)+2d(n-1)=2\cdot 10^{n-1}+(a(n-1)+c(n-1))$$
Donde la última igualdad se debe a que $(a+b+c+d)(k)$ contempla todos los $10^{n-1}$ números de $n-1$ dígitos.
Ahora, notemos que $(a+c)(k)$ contempla a todos los números que cumplen ii. (pueden cumplir i. o no).
Para contar la cantidad de números que cumplen ii., consideremos los $n-2$ últimos dígitos y notemos que si estos forman un número que cumple ii., podemos agregar $0$, $1$, $4$, $5$, $8$ u $9$ al principio, si no, podemos agregar $2$, $3$, $6$ o $7$, es decir:
$$(a+c)(n-1)=6(a+c)(n-2)+4(10^{n-1}-(a+c)(n-2))=2(a+c)(n-2)+4\cdot 10^{n-1}$$
Más aún, es claro que $(a+c)(1)=4=0,5\cdot 10-1$, y si asumimos que $(a+c)(k)=0,5\cdot 10^k-2^{k-1}$, entonces
$$(a+c)(k+1)=2(0,5\cdot 10^k-2^{k-1})+4\cdot 10^{k}=5\cdot 10^k-2^{k}=0,5\cdot 10^{k+1}-2^{k}$$
Por lo que apelando a inducción demostramos que $(a+c)(k)=0,5\cdot 10^k-2^{k-1}$ para todo $k$. En particular, con $k=n-1$,
$$(a+c)(n-1)=0,5\cdot 10^{n-1}-2^{n-2}$$
Y si agregamos esto a lo anterior:
$$a(n)=2\cdot 10^{n-1}+0,5\cdot 10^{n-1}-2^{n-2}=2,5\cdot 10^{n-1}-2^{n-1}=f(n)$$
Es decir, hay $f(n)$ puntos rojos.$^1$
Finalemente, por lo que vimos primero, cada cuaterna especial contiene exactamente un número rojo. Por lo que vimos segundo, hay $f(n)$ puntos rojos. Entonces, queda clarísimo que si usara más de $f(n)$ cuaternas especiales, habría dos que, por Palomar, usarían el mismo punto rojo, lo cual contradice el enunciado. Con esto, demostramos que la cota $f(n)=2,5\cdot 10^{n-1}-2^{n-2}$ es óptima.
$^1$ Muy probablemente haya una forma más sencilla de contar. Si la encuentro la cambio...
El problema es muy simpático, y la solución no es nada del otro mundo, sólo tiene muchas cuentas.
Lo más divertido del problema es que es muy fácil de graficar. Por ejemplo, si $n=2$, consideremos un tablero de $10\times 10$, con filas y columnas numeradas del $0$ al $9$. En cada casilla escribimos el dígito de la columna seguido del dígito de la fila. Entonces, una cuaterna especial se transforma en cuatro números consecutivos, o, como le dicen a quienes les gustan los tableros, una ficha $1\times 4$. Y esto es un problema bastante conocido, que está, por ejemplo, en: https://www.omaforos.com.ar/viewtopic.p ... 190#p20421 (ver la solución inmediatamente abajo).
Entonces, la moraleja de la solución es intentar encontrar algo parecido (una coloración módulo $4$) que resuelva el problema de exactamente la misma manera.
Por ejemplo, en un tablero $4\times 4$, las casillas rojas forman una diagonal del tablero.
Más difícil es quizás el cubo, pero algo así funciona: tomamos un cubo $4\times 4\times 4$, lo podemos dividir en $8$ cubitos $2\times 2\times 2$, y tomar cuatro de ellos que no tengan ninguna cara en común (a.k.a. todos los de un mismo color en coloración de ajedrez). Entonces, si cada cubo $2\times 2\times 2$ coloreas de rojo cuatro cubitos que formen una distribución idéntica a los cuatro cubos $2\times 2\times 2$ (es decir, de un mismo color en ajedrez y que tenga la misma orientación que la otra elección), esta coloración ($16$ cubitos rojos) si se repite periódicamente hasta llenar un $10\times 10\times 10$, se obtiene una coloración que alcanza la cota.
A partir de acá, es sólo ver un poco la situación y generalizarla... Y terminar el problema...
Agrego un comentario. Una idea que suele funcionar para saber si un tablero se puede cubrir con ciertos rectángulos es colorear con números complejos. Esta idea se extiende fácil a más dimensiones.
