Epidemie
Anche stavolta parlo di un problema tratto da Numberplay. Il matematico ungherese naturalizzato britannico Béla Bollobás racconta:
Un’epidemia si sta propagando in una scacchiera 12×12. Inizialmente solo alcune caselle sono infette: una casella infetta lo rimarrà per sempre, e una casella non infetta si infetterà se avrà almeno due caselle confinanti infette. Per “confinanti” si intende “che la toccano su un lato”, quindi una casella ha al più quattro caselle confinanti. Qual è il numero minimo di caselle inizialmente infette che potrà infettare tutta la scacchiera?
Per la cronaca, è possibile partire da una configurazione di ben 132 caselle infettate (tutte tranne la riga superiore della scacchiera) e non riuscire a infettare tutta la scacchiera: è facile vedere che la riga superiore non verrà mai infettata, poiché ogni casella ha solo un vicino infetto. Ma il killer della tastiera può scegliere opportunamente i punti di infezione e usarne molto meno. Volete sapere come?
