Se tiene un tablero de $10 \times 10$ dividido en casillas de $1 \times 1$. Un punto luminoso en un vértice de un cuadrado de $1 \times 1$ ilumina a todos los cuadrados de $1 \times 1$ a los que ese vértice pertenece. Hallar la cantidad mínima de puntos luminosos que se necesitan para que todos los cuadrados de $1 \times 1$ del tablero estén iluminados aún en el caso de que uno cualquiera de los puntos luminosos, no sabemos cuál, deje de funcionar.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore! Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Tenemos una cuadrícula de $11\times 11$ puntos. Si pintamos las columnas pares tendremos pintados $11\times 5=55$ puntos y es claro que ese ejemplo funciona porque cada cuadrado tiene $2$ puntos pintados.
Ahora probemos que $55$ es el mínimo: consideramos una fila de cuadrados. Tenemos 3 posibilidades:
1) Hay 11 o más pintados.
2) Hay 10 pintados. En este caso la única forma de que todos los cuadrados tengan al menos 2 puntos pintados es pintando las columnas pares de esa fila.
3) Hay menos de 10 pintados. En este caso nos aseguramos tener un cuadrado con un sólo punto pintado y fallaría. Por lo tanto no puede haber menos de 10 pintados en cada fila de cuadrados.
Si todas las filas tienen 11 o más pintados, entonces mirando las filas de cuadrados 2, 4, 6, 8, 10, que son disjuntas, tendríamos al menos $55$ puntos pintados, como queríamos.
Si hay filas con 10, vimos que la única configuración posible de esa fila es tener pintadas las columnas pares. Supongamos que hay una fila de cuadrados, la $i$, de 10 puntos pintados y entonces están pintados los puntos $(i,2),(i,4),...,(i,10),(i+1,2),...,(i+1,10)$.
Miramos cualquier columna de cuadrados $j$, y esa columna no puede tener 10 puntos pintados, porque en ese caso esa columna debería tener sólo las filas de puntos pares pintadas $(2,j),...,(10,j),(2,j+1),...,(10,j+1)$ y eso no ocurre porque sabemos que están pintados o bien los puntos $(i,j)$ e $(i+1,j)$ o bien los puntos $(i,j+1)$ e $(i+1,j+1)$.
Por lo tanto, si hay una fila de cuadrados con 10 puntos pintados, todas las columnas deben tener al menos 11 puntos pintados. Seleccionando las columnas 2, 4, 6, 8, 10, tenemos al menos $55$ puntos pintados.
Sea $n\in \mathbb{N}$. Un tablero $T_n$ es un tablero de $n\times n$. Un tablero $L_n$ es el tablero que se obtiene al quitar un tablero $T_{n-1}$ de un tablero $T_n$, es decir, una $L$ de lados $n$. Escribo $T_n=T_{n-1}+L_n$.
Llamo fichas a los puntos luminosos, digo que una casilla está cubierta cuando tiene al menos dos fichas en sus vértices y que un tablero está lleno cuando todas sus casillas están cubiertas. Que una casilla esté cubierta es equivalente a que esté iluminada aunque uno de sus puntos luminosos falle, y no podemos asegurar que una casilla no cubierta se mantenga iluminada, pues podría fallar el único punto que la ilumina, o no tener ningún punto que la ilumine. Luego, que un tablero esté lleno es equivalente a que todas las casillas del tablero estén iluminadas aunque alguno de los puntos luminosos falle.
Sea $X$ un tablero dividido en cuadrados de $1\times 1$, en el que cada cuadrado comparte un lado con al menos otro cuadrado. Llamo $C(X)$ a la mínima cantidad de fichas que necesito para llenar $X$.
Caso base: $n=1$
Tenemos que poner $2$ fichas en $a$ y $2$ fichas en $b$, luego, necesitamos al menos $4$ fichas. Pero hay a lo sumo (puede ser que no la coloquemos ahí) una ficha que estamos contando tanto en $a$ como en $b$, que es la que está en el vértice en común de las $3$ casillas de $L_2$. Luego, necesitamos al menos $4-1=3$ fichas.
Caso base L.png
Paso inductivo: Supongamos que vale para $n=k$, veamos que vale para $k+1$
El $L_{2k+2}$ se forma agregando $2$ casillas en cada extremo de $L_{2k}$
L_(2k+2).png
Por hipótesis inductiva podemos cubrir $L_{2k}$ con $4k-1$ fichas. La última casilla a la derecha y la última casilla arriba de $L_{2k+2}$ no están en contacto con ninguna casilla de $L_{2k}$, por lo tanto, no están en contacto con ninguna ficha, luego $C(L_{2k+2})\geqslant C(L_{2k})+C(T_1)+C(T_1)$. Como $C(T_1)=2$, entonces $C(L_{2k+2})\geq 4k-1+2+2=4(k+1)-1$.
Con este ejemplo vemos que nos alcanza con $4(k+1)-1$ fichas.
L.png
Como todas las casillas están cubiertas, el tablero está lleno y el ejemplo funciona.
La inducción está completa.
Parte $2$: Demostrar que $C(T_{2n})=\binom{2n+1}{2}$
Caso base: $n=1$
Si no ponemos ninguna ficha en el centro de $T_2$, cada ficha toca a lo sumo $2$ casillas. Tenemos $4$ casillas, entonces necesitamos por lo menos $8$ fichas para llenar $T_2$, pero como las fichas tocan a lo sumo $2$ casillas, estamos contando cada ficha a lo sumo dos veces, por lo tanto necesitamos al menos $\frac{8}{2}=4$ fichas.
Si ponemos una ficha en el centro de $T_2$, cada casilla necesita al menos una ficha más, entonces necesitamos al menos $4$ fichas más; pero como las fichas tocan a lo sumo $2$ casillas, estoy contando cada ficha a lo sumo $2$ veces, luego, necesitamos por lo menos $\frac{4}{2}=2$ fichas más. Por lo tanto necesitamos al menos $1+2=3=\binom{3}{2}$ fichas.
Caso base T.png
Paso inductivo: Supongamos que vale para $n=k$, veamos que vale para $k+1$.
Por definición de $T_{2k+2}$ tenemos $T_{2k+2}=T_{2k+1}+L_{2k+2}$ (*)
Por definición de $T_{2k+1}$ tenemos $T_{2k+1}=T_{2k}+L_{2k+1}$ (**)
De (*) y (**) tenemos $T_{2k+2}=T_{2k}+L_{2k+1}+L_{2k+2}$
T_(2k+2).png
Ninguna de las casillas de $L_{2k+2}$ está en contacto con alguna casilla de $T_{2k}$, entonces no tienen ninguna ficha en común. Luego, $C(T_{2k+2})\geqslant C(T_{2k})+C(L_{2k+2})$. Por hipótesis inductiva tenemos $C(T_{2k})=\binom{2k+1}{2}$, por lo demostrado en la Parte $1$ tenemos $C(L_{2k+2})=4(k+1)-1$.
Entonces $C(T_{2k+2})\geqslant C(T_{2k})+C(L_{2k+2})=\binom{2k+1}{2}+4(k+1)-1=\frac{2k(2k+1)}{2}+4(4k+1)-1=\frac{2k(2k+1)+8(k+1)-2}{2}=\frac{4k^2+2k+8k+8-2}{2}=\frac{4k^2+4k+6k+6}{2}=\frac{2k(2k+2)+3(2k+2)}{2}=\frac{(2k+2)(2k+3)}{2}=\binom{2k+3}{2}=\binom{2(k+1)+1}{2}$
Con este ejemplo vemos que nos alcanza con $\binom{2(k+1)+1}{2}$ fichas.
T.png
Como todas las casillas están cubiertas, el tablero está lleno y el ejemplo funciona.
La inducción está completa.
Por lo tanto para $n=5$ tenemos $C(T_{10})=\binom{11}{2}=55$
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Si hay $2$ puntos luminosos en un mismo cuadrado pintamos el segmento que los une, vamos a tener dos tipos de segmentos, las rayas son los que coinciden un un lado del cuadrado mientras que las diagonales unen los vértices opuestos del cuadrado.
Una diagonal nos asegura solo un cuadrado mientras que la raya uno o dos.
Como hay $4n^2$ casillas se necesitan al menos $2n^2$ rayas para asegurar todas las casillas.
Llamamos segmento de longitud $L$ a $L$ rayas unidas donde solo se forman ángulos de 180 grados, la mayor longitud de uno de estos segmentos es de $2n$
Un segmento de longitud $L$ utiliza $L+1$ puntos luminosos.
Si dos segmentos comparten un punto luminoso debe haber una casilla con $2$ rayas por lo tanto si se utilizan $2n^2$ rayas va a haber una casilla que no tiene ninguna raya por lo que se va a tener que agregar una raya o diagonal más y agregar una de estas implica agregar uno o dos puntos luminosos por lo tanto el punto luminoso que comparten los dos segmentos mencionados va a aparecer por algún lado y tal ves con alguno extra.
Llamamos $a_i$ a la cantidad de segmentos de longitud $i$.
$a_1+2a_2+...+2na_{2n}\geq 2n^2$
Sea $p$ la cantidad de puntos luminosos.
$p\geq 2a_1+3a_2+...+(2n+1)a_{2n}\geq 2n^2+a_1+a_2+...+a_{2n}$
Por lo tanto $p$ es mínimo cuando se utiliza la menor cantidad de segmentos, lo cual pasa cuando usas $n$ segmentos de longitud $2n$, entonces $p\geq 2n^2+n$.
En el caso $2n=10$, $p\geq 2\times 5^2+5=55$, el ejemplo es el mismo que Martin.
Notemos que la condicion del enunciado se traduce en que cada casilla tenga al menos dos vertices como puntos luminosos. Por lo tanto la cantidad de puntos luminosos es al menos el doble de la cantidad de casillas marcadas en el tablero, menos la cantidad de vertices que son comunes a dos casillas marcadas. Como hay $30$ casillas marcadas, y $5$ vertices son comunes a $2$ casillas, la cantidad de puntos luminosos es al menos $55$.
