Illuminare un Esagono — Un Puzzle di Propagazione
Immagina una griglia a nido d’ape: un esagono grande composto da celle esagonali più piccole, con lato di 5 celle. All’inizio, tutte le celle sono spente.
C’è una sola regola:
Una cella si accende se e solo se è circondata da esattamente 3 celle già accese.
La domanda è: qual è il numero minimo di celle da accendere all’inizio, e come disporle, affinché — dopo un certo numero di iterazioni — l’intera griglia risulti illuminata?
La griglia esagonale con lato 5 — all’inizio tutte le celle sono spente
Clicca qui per la soluzione
Una delle possibili configurazioni iniziali che illumina l’intera griglia
Le soluzioni valide sono più d’una, ma tutte condividono una proprietà fondamentale: il numero minimo di celle inizialmente accese è 9.
Non è un numero scelto a caso. Per capire da dove viene, bisogna introdurre un concetto chiave: l’invariante del perimetro.
L’invariante del perimetro
Osserva cosa succede al perimetro complessivo delle celle accese ad ogni iterazione. Quando una nuova cella si accende — cioè quando trova esattamente 3 vicine illuminate — il perimetro totale non aumenta mai. Questo è il cuore del ragionamento: il perimetro delle celle accese è una quantità non crescente nel tempo.
Questo ci dà un vincolo preciso: affinché la luce si propaghi fino ai bordi dell’esagono grande, il perimetro della configurazione iniziale deve essere almeno pari al perimetro dell’esagono grande stesso.
1° Iterazione di accensione che mostra come il perimetro si conservi dopo ogni accensione
Il calcolo
L’esagono grande con lato 5 ha un perimetro di 54 lati.
Ogni cella esagonale piccola ha 6 lati. Se le celle iniziali sono isolate (non contigue tra loro), ciascuna contribuisce con tutti e 6 i propri lati al perimetro totale. Servono quindi almeno:
$$ \frac{54}{6} = 9 \text{ celle}$$
E 9 celle non contigue danno esattamente $9 \times 6 = 54$ lati di perimetro — il minimo indispensabile.
La corrispondenza tra il perimetro iniziale e quello dell’esagono grande
Conclusione
La condizione necessaria e sufficiente affinché tutta la griglia si illumini è che la configurazione iniziale abbia un perimetro totale pari a quello dell’esagono grande. Il numero minimo di celle per soddisfare questa condizione è 9, disposte in modo che non si tocchino tra loro.