Noventa y nueve casillas infectadas frente a un tablero de diez mil. Si están bien elegidas, ¿podrá el contagio apoderarse de todas?
La infección del tablero
Enunciado
En un tablero de \(100\times100\), puedes elegir exactamente 99 casillas para que empiecen infectadas.
Después, el contagio avanza por rondas: en cada ronda, toda casilla sana que comparta lado con al menos dos casillas infectadas pasa a estar infectada. Las casillas infectadas nunca se curan.
¿Puedes elegir las 99 casillas iniciales de modo que, tarde o temprano, todo el tablero quede infectado?
Ver solución
Solución
Respuesta: No. Ninguna elección de 99 casillas iniciales puede acabar infectando todo el tablero.
La clave no está en contar cuántas casillas están infectadas, sino en medir la frontera de la infección.
Llamemos \(P\) al número de lados unitarios que cumplen una de estas dos condiciones:
- separan una casilla infectada de una casilla sana;
- separan una casilla infectada del exterior del tablero.
1. La frontera nunca puede aumentar.
Supongamos que se infecta una casilla que tiene \(k\ge2\) vecinos infectados por un lado.
Antes de infectarse, los \(k\) lados que comparte con esos vecinos pertenecen a la frontera. Al infectarse, esos lados dejan de separar una casilla infectada de una sana, así que desaparecen de la cuenta.
Los otros \(4-k\) lados pasan a formar parte de la nueva frontera: dan a casillas sanas o, si la casilla está en el borde, al exterior del tablero.
Por tanto,
Como \(k\ge2\),
Así, cada nueva infección mantiene o reduce la frontera, pero nunca la aumenta.
Aunque durante una ronda se infecten varias casillas simultáneamente, podemos examinarlas una tras otra en cualquier orden. Cada una ya tenía al menos dos vecinos infectados al comenzar la ronda, y procesar antes otras infecciones solo puede aumentar ese número. Por tanto, la misma desigualdad sigue siendo válida.
2. La frontera inicial es demasiado pequeña.
Cada una de las 99 casillas infectadas puede aportar como máximo cuatro lados a la frontera. Luego
Esta cota vale sea cual sea la posición elegida para las 99 casillas.
3. El tablero completamente infectado necesitaría una frontera mayor.
Si las 10.000 casillas estuvieran infectadas, ningún lado interior pertenecería a la frontera. Solo quedaría el contorno exterior del tablero.
Cada uno de sus cuatro lados mide 100 unidades, por lo que
Pero \(P\) empieza siendo como máximo 396 y nunca puede aumentar. No puede terminar valiendo 400.
Por tanto, es imposible infectar por completo el tablero partiendo únicamente de 99 casillas.
Idea esencial: la infección puede ocupar cada vez más casillas, pero no puede crear la cantidad de frontera que necesitaría el tablero completamente infectado.